题目描述

题目译自 BalticOI 2015 Day1 Bowling(BOW)，原题面见附加文件。
如欲转载翻译，请注明翻译者信息及转载出处。

Byteasar 是一个保龄球迷，也是个数据迷。他记录下了一些过去保龄球比赛的结果。不幸的是，一些记录中的字符被污损了，因此看不清。Byteasar 请你写一个程序来计算与他的记录相符的不同比赛数目。

保龄球规则

一场保龄球比赛有 $n$ 局（frame）：$n-1$ 局普通局和一局最终局。在一个典型的比赛中 $n=10$。在每局比赛最初，有 $10$ 个保龄球瓶正立放在球道末端，并且一个选手有不多于 $2$ 次（最终局有 $3$ 次）掷球机会（shots）去尽可能击倒更多数目的保龄球瓶。每局比赛被 $2$ 个（对于普通局）或 $3$ 个（对于最终局）字符表示。

对于每次投掷，选手会获得与他击倒保龄球瓶总数相等的基础分（basic points）。每局选手获得的基础分是这局内每一次投掷获得基础分的和。如果在一个普通局中 $10$ 个球瓶均被击倒（因此获得了 $10$ 分基础分），这个选手会获得奖励分（bonus points）。

对于一个普通局，规则如下：

• 如果一个选手在一局的第一次投掷后击倒了所有 $10$ 个球瓶，就称他全中（strike），并且这局比赛结束。下两次投掷获得的基础分的和将作为他的奖励分。一次全中记为 x- ；
• 如果一个选手用了一局中的两次投掷机会击倒了所有球瓶，就称他补中（spare）。下一次投掷获得的基础分将作为他的奖励分。一次补中记为 A/，其中 $A$ 是一个数字，描述他本局中第一次投掷击倒的球瓶数目；
• 如果两次投掷后击倒的球瓶数不多于 $9$，这个选手只获得基础分，这样的一局被记为 AB，其中 $A$ 表示本局中第一次投掷击倒球瓶数，$B$ 表示本局中第二次投掷击倒球瓶数（$A+B\lt 10$）。

注意奖励分只包含在获得全中或补中的局中，忽略奖励分取决于下一局中投掷的事实。

最终局的规则如下：

• 在本局，选手最初有两次投掷机会。如果前两次投掷击倒的球瓶数不多于 $9$，这局比赛结束。否则（如果头两次投掷是一个补中或第一次投掷是一个全中），在本局，这个选手将获得第三次投掷的机会。每当这三次投掷中哪一次击倒了全部球瓶，下一次投掷时球瓶就会恢复初始状态。最终局的得分是击倒球瓶的数目和（注意最终局没有因补中或全中获得的奖励分）；
• 总的说来，最终局共有以下 $7$ 种可能的比赛结果（$A$ 和 $B$ 表示一个一位的数字）：

每一次比赛被一个长为 $2n+1$ 的字符串描述。在比赛最后每局的得分才可被计算。例如，对于一次 $n=10$ 的比赛，用 08x-7/2/x-x-23441/0/x 描述，选手每局的得分和总分如下：

输入格式

输入的第一行有一个正整数 $q$，表示需要考虑的测试数据组数。接下来的 $3q$ 行包含对输入数据的描述。每组数据有三行。

每组数据的第一行包含一个正整数 $n$，表示局数。第二行为一个长度为 $2n+1$ 的字符串，表示 Byteasar 的笔记中对比赛的记录。污损的字符被 ? 替代。第三行包含 $n$ 个正整数，表示每局比赛后的累计得分，两个数字之间用一个空格隔开。对于每个数字，要么所有位都是可读的，要么所有数位都是污损的。污损的数字用 $-1$ 替代。

输出格式

你的程序应该输出 $q$ 行，对于每组输入数据按输入顺序输出一行。

对于每组数据，你的程序应输出一个整数：与输入数据相符的可能的不同比赛数目。两场比赛不同当且仅当它们至少一掷是不同的。那就是说，用 $2n+1$ 个字符描述的比赛状态是不一样的。你可以假设至少有一场比赛符合输入，并且结果不会超过 $64$ 位有符号整数的大小范围。

样例

样例输入 1

2
10
08x-7/2/x?x-23??1/???
8 -1 40 60 82 97 102 110 120 140
5
x-x-23?/00-
22 37 42 52 52

样例输出 1

9
10

样例说明 1

对于第一组测试数据，在第 $5$ 局接着字符 x 之后的唯一可能字符是 -。在第 $8$ 局选手共获得 $8$ 分。因此共有 $9$ 种可能获得这个分数：$0+8,1+7,\cdots ,8+0$。第 $9$ 局没有获得奖励分，因此，最终局的第一掷没有得分。为了在最后两掷获得 $20$ 分，唯一的可能是第二掷补中，第三掷全中。因此共有 $9$ 种不同合法的比赛符合输入数据。

对于第二组数据，任意的 $0$ 到 $9$ 的字符均符合输入数据。

样例输入/输出 2

参见附加文件 bow_sample2.in/ans

数据范围与提示

本题采用子任务式测评，只有一个子任务内所有测试点均正确才可获得此子任务的分数。

对于全部子任务，满足 $1\le q\le 25,2\le n\le 10$。

对于每个子任务满足的条件如下：