Bowling

Byteasar likes bowling and statistics. He wrote down the results of a few bowling games he played, but some characters in the notes are blurred and unreadable. Write a program that counts the distinct games consistent with his notes.

Rules of bowling

A game has $n$ frames: $n - 1$ simple frames and one final frame. A typical game has $n = 10$. At the start of every frame 10 pins stand at the end of the lane, and the player rolls the ball to knock down as many pins as possible. A simple frame gives at most two shots and the final frame at most three. A simple frame is written with two characters, the final frame with three.

The basic points of a shot are the number of pins it knocks down. The basic points of a frame are the sum of the basic points of its shots. Knocking down all 10 pins in a simple frame earns 10 basic points plus bonus points.

A simple frame follows these rules.

• The first shot knocks down all 10 pins: this is a strike and the frame ends. The bonus points are the sum of the basic points of the next two shots. A strike is written x-.
• The two shots of the frame together knock down all 10 pins: this is a spare. The bonus points are the basic points of the next shot. A spare is written A/, where A is the one-digit number of pins knocked down by the first shot.
• The two shots knock down 9 pins or fewer: the player earns only basic points, and the frame is written AB, where A is the number of pins from the first shot, B the number from the second, and $A + B < 10$.

Bonus points count toward the frame where the strike or the spare happened, even though their value comes from shots in later frames.

The final frame follows these rules.

• The player starts with two shots. If those two shots knock down 9 pins or fewer, the frame ends. If the two shots make a spare, or the first shot is a strike, the player takes a third shot. Whenever a shot knocks down every standing pin, 10 pins are set up again for the next shot. The score of the final frame is the total number of pins it knocks down, and strikes and spares earn no bonus points there.
• The final frame has seven possible forms. A and B are one-digit numbers.

A game is written as a sequence of $2n + 1$ characters. The running total after each frame follows from that sequence. For example, the game 08x-7/2/x-x-23441/0/x with $n = 10$ scores like this.

The first line has one integer $q$ ($1 \le q \le 25$), the number of test cases. Each test case takes three lines.

The first line of a test case has one integer $n$ ($2 \le n \le 10$), the number of frames. The second line has the $2n + 1$ characters that describe the game in Byteasar's notes, with every blurred character replaced by ?. The third line has $n$ integers separated by spaces, the running total after each frame. In each of these numbers either every digit is readable or every digit is blurred, and a number whose digits are all blurred is replaced by -1.

For each test case print one line with the number of distinct games that agree with it, in the order of the input.

Two games differ when at least one shot differs, that is, when their $2n + 1$ character descriptions differ. At least one game agrees with each test case in the input. Every answer fits in a signed 64-bit integer.

The first example input has two test cases.

In the first one, frame 5 can only be x-, since - is the one character that can follow x. Frame 8 scores 8 points, so its two shots are $0 + 8$, $1 + 7$, ..., $8 + 0$, nine possibilities in all. Frame 9 earns 0 bonus points, so the first shot of the final frame knocks down no pins. The only way to score 20 with the remaining two shots is a spare followed by a strike. Nine games therefore agree with the notes.

In the second test case, every digit from 0 to 9 fits the blurred position.