Byteasar 既是保龄球爱好者，也是统计学爱好者。他记录了几场过去保龄球比赛的结果。不幸的是，笔记中的一些字符模糊不清，无法辨认。Byteasar 请你编写一个程序，计算出与他的笔记相符的不同比赛结果的数量。

保龄球规则

一场保龄球比赛包含 $n$ 局：$n-1$ 局普通局和一局最终局。在典型的比赛中 $n=10$。每局开始时，球道末端竖立着 10 个球瓶，选手最多有两次（最终局为三次）投球机会（击球）来尽可能多地击倒球瓶。每局由两个（普通局）或三个（最终局）字符表示。

对于每次击球，选手获得的“基本分”是该次击球击倒的球瓶总数。选手在每一局的“基本分”是该局所有击球的基本分之和。如果在一局普通局中击倒了全部 10 个球瓶（因此获得了 10 点基本分），选手将获得额外的奖励分。

普通局的规则如下： 如果选手在第一球就击倒了全部 10 个球瓶，则该局结束，称为“全中”（strike）。作为奖励分，她获得接下来两次击球的基本分之和。全中记为 “x-”。 如果选手在两球内击倒了全部 10 个球瓶，则称为“补中”（spare）。作为奖励分，她获得下一次击球的基本分。补中记为 “A/”，其中 $A$ 是一个数字，表示该局第一球击倒的球瓶数。 * 如果两球后击倒的球瓶总数不超过 9 个，则选手仅获得基本分，该局记为 “AB”，其中 $A$ 是第一球击倒的球瓶数，$B$ 是第二球击倒的球瓶数（$A+B < 10$）。

注意，奖励分计入获得全中或补中的那一局的得分中，无论奖励分的具体数值取决于后续局中的哪些击球。

最终局的规则如下： 最初选手在该局有两次击球机会。如果两次击球击倒的球瓶总数不超过 9 个，则该局结束。否则（如果前两球是补中，或第一球是全中），选手在该局获得第三次击球机会。每当选手在三次击球中的任意一次击倒全部球瓶时，球瓶会重置为初始状态以供下一次击球。最终局的得分是击倒的球瓶总数（注意，最终局不会因全中或补中获得额外奖励分）。 最终局共有七种可能的配置，结果如下（$A$ 和 $B$ 代表一位数字）：

每场比赛描述为一个包含 $2n+1$ 个字符的序列。在比赛结束时，可以计算出每一局后的累计总分。例如，对于 $n=10$ 局的比赛，描述为 “08x-7/2/x-x-23441/0/x”，选手各局后的得分如下：

输入格式

输入的第一行包含一个整数 $q$ ($1 \le q \le 25$)，表示测试用例的数量。接下来的 $3q$ 行包含测试用例的描述。每个测试用例由三行输入组成。 第一行包含一个整数 $n$ ($2 \le n \le 10$)，表示局数。 第二行包含一个长度为 $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

说明

在第一个样例中，第 5 局字符 “x” 之后唯一可能的字符是 “-”。在第 8 局中，选手总共获得了 8 分。因此，这个总和有 9 种可能的组成方式：0+8, 1+7, ..., 8+0。第 9 局没有奖励分。因此，最终局的第一球没有得分。为了在最后两球中获得 20 分，唯一的可能性是补中，且最终局最后一球为全中。因此，对应此输入数据有 9 种不同的有效比赛。 在第二个样例中，0 到 9 的任何字符都与输入数据相符。

子任务