Description

Format

Input

The first line of input contains one integer Q(1<=Q<=25), specifying the number of test cases to consider. The following 3Q lines of input contain descriptions of test cases. Each test case is described by three lines of input.

The first line of a test case description contains one integer N(2<=N<=10), specifying the number of frames. The second line contains a sequence of 2N+1 characters which denotes the game description from Byteasar's notes. Blurry characters are replaced by "?" characters. The third line contains n integers, the total number of points after each frame, separated by spaces. In each number either all digits are readable, or all digits are blurry. Numbers in which all digits are blurry are replaced by "-1".

Output

Your program should output q lines, one line per each test case in the same order as in the input.

For each test case your program should write one integer: the number of possible distinct games corresponding to the test case. Two games are considered different if and only if they differ in at least one shot, that is, their 2N+1 -character game descriptions are different. You can assume that there is at least one game consistent with each test case in the input. You can assume that the result fits into 64-bit signed integer type.

Samples

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

9
10

Limitation

Explanation to the example: In the first case, in frame 5 after the character "x" the only possible character is "-". In frame 8 the player got 8 points in total. Thus there are 9 possibilities how this sum could have been obtained:0+8,1+7,….8+0. There were no bonus points in frame 9. Therefore, there were no points on the first shot of the final frame. To obtain 20 points in the last two shots, the only possibility is a spare with a following strike in the last shot of the frame. Therefore there are 9 different valid games which correspond to this input data.

In the second case, any character from 0 to 9 is consistent with the input data.