볼링 | cho.sh

문제

바이트아사르는 볼링과 통계를 좋아한다. 그는 예전에 친 볼링 경기 몇 판의 결과를 공책에 적어 두었다. 그런데 글자 몇 개가 번져서 읽을 수 없다. 공책의 기록과 맞아떨어지는 서로 다른 경기가 몇 가지인지 세는 프로그램을 작성하라.

볼링 규칙

한 경기는 프레임 $n$ 개로 이루어진다. 앞의 $n - 1$ 개는 일반 프레임이고 마지막 하나는 최종 프레임이다. 보통 경기는 $n = 10$ 이다. 각 프레임을 시작할 때 레인 끝에 핀 10개를 세워 놓고, 선수는 공을 굴려 핀을 최대한 많이 쓰러뜨린다. 투구는 일반 프레임에서 최대 두 번, 최종 프레임에서 최대 세 번이다. 일반 프레임은 문자 두 개로, 최종 프레임은 문자 세 개로 적는다.

한 투구로 쓰러뜨린 핀의 개수가 그 투구의 기본 점수다. 프레임의 기본 점수는 그 프레임에서 던진 모든 투구의 기본 점수를 더한 값이다. 일반 프레임에서 핀 10개를 모두 쓰러뜨리면 기본 점수 10점에 더해 보너스 점수를 얻는다.

일반 프레임의 규칙은 다음과 같다.

첫 투구로 핀 10개를 모두 쓰러뜨리면 스트라이크이고 프레임이 끝난다. 보너스 점수는 다음 두 투구의 기본 점수 합이다. 스트라이크는 x-로 적는다.
두 투구로 핀 10개를 모두 쓰러뜨리면 스페어다. 보너스 점수는 다음 한 투구의 기본 점수다. 스페어는 A/로 적고, A는 첫 투구로 쓰러뜨린 핀의 개수를 나타내는 한 자리 숫자다.
두 투구로 쓰러뜨린 핀이 9개 이하이면 기본 점수만 얻고, 이 프레임은 AB로 적는다. A는 첫 투구, B는 둘째 투구로 쓰러뜨린 핀의 개수이며 $A + B < 10$ 이다.

보너스 점수는 스트라이크나 스페어가 나온 프레임의 점수에 포함된다. 그 값이 뒤 프레임의 투구로 정해지더라도 마찬가지다.

최종 프레임의 규칙은 다음과 같다.

선수는 먼저 두 번 던진다. 두 투구로 쓰러뜨린 핀이 9개 이하이면 프레임이 끝난다. 두 투구가 스페어가 되거나 첫 투구가 스트라이크이면 세 번째 투구를 던진다. 세 투구 중 어느 투구로든 서 있는 핀을 모두 쓰러뜨리면 다음 투구를 위해 핀 10개를 다시 세운다. 최종 프레임의 점수는 쓰러뜨린 핀의 총 개수이고, 스트라이크나 스페어로 얻는 보너스 점수는 없다.
최종 프레임의 표기는 다음 일곱 가지다. A와 B는 한 자리 숫자다.

표기	설명	프레임 점수
`xxx`	스트라이크 세 번	$30$
`xxA`	스트라이크 두 번과 핀 $A$ 개를 쓰러뜨린 투구	$20 + A$
`xA/`	스트라이크 한 번과 첫 투구로 핀 $A$ 개를 쓰러뜨린 스페어	$20$
`xAB`	스트라이크 한 번과 핀 $A$ 개, $B$ 개를 쓰러뜨린 두 투구 ( $A + B < 10$ )	$10 + A + B$
`A/x`	첫 투구로 핀 $A$ 개를 쓰러뜨린 스페어와 스트라이크	$20$
`A/B`	첫 투구로 핀 $A$ 개를 쓰러뜨린 스페어와 핀 $B$ 개를 쓰러뜨린 마지막 투구	$10 + B$
`AB-`	핀 $A$ 개, $B$ 개를 쓰러뜨린 두 투구 ( $A + B < 10$ )	$A + B$

경기 하나는 문자 $2n + 1$ 개로 적는다. 경기 기록에서 각 프레임까지의 누적 점수를 계산할 수 있다. 예를 들어 $n = 10$ 이고 경기가 08x-7/2/x-x-23441/0/x이면 점수는 다음과 같다.

프레임	표기	기본 점수	보너스 점수	프레임 점수	누적 점수
1	`08`	$0 + 8$	$0$	$8$	$8$
2	`x-`	$10$	$7 + 3$	$20$	$28$
3	`7/`	$7 + 3$	$2$	$12$	$40$
4	`2/`	$2 + 8$	$10$	$20$	$60$
5	`x-`	$10$	$10 + 2$	$22$	$82$
6	`x-`	$10$	$2 + 3$	$15$	$97$
7	`23`	$2 + 3$	$0$	$5$	$102$
8	`44`	$4 + 4$	$0$	$8$	$110$
9	`1/`	$1 + 9$	$0$	$10$	$120$
최종	`0/x`	$0 + 10 + 10$	$0$	$20$	$140$

입력

첫 줄에 테스트 케이스의 개수 $q$ ( $1 \le q \le 25$ )가 주어진다. 이어서 테스트 케이스가 세 줄씩 주어진다.

각 테스트 케이스의 첫 줄에는 프레임의 개수 $n$ ( $2 \le n \le 10$ )이 주어진다. 둘째 줄에는 공책에 적힌 경기를 나타내는 문자 $2n + 1$ 개가 주어지며, 번져서 읽을 수 없는 문자는 ?로 바뀌어 있다. 셋째 줄에는 각 프레임까지의 누적 점수 $n$ 개가 공백으로 구분되어 주어진다. 각 수는 모든 자리를 읽을 수 있거나 모든 자리를 읽을 수 없다. 모든 자리를 읽을 수 없는 수는 -1로 바뀌어 있다.

출력

테스트 케이스마다 한 줄에 기록과 맞아떨어지는 서로 다른 경기의 개수를 입력에 주어진 순서대로 출력한다.

두 경기는 투구가 하나라도 다르면, 즉 문자 $2n + 1$ 개로 된 경기 기록이 다르면 서로 다르다고 본다. 입력의 각 테스트 케이스에는 기록과 맞아떨어지는 경기가 적어도 하나 있다. 답은 64비트 부호 있는 정수에 들어간다.

힌트

첫 번째 예제 입력에는 테스트 케이스가 두 개 있다.

첫 테스트 케이스에서 5번 프레임은 x 다음에 -만 올 수 있다. 8번 프레임의 점수는 8점이므로 $0 + 8$ , $1 + 7$ , ..., $8 + 0$ 의 아홉 가지가 가능하다. 9번 프레임은 보너스 점수가 0점이므로 최종 프레임의 첫 투구는 핀을 하나도 쓰러뜨리지 못했다. 남은 두 투구로 20점을 얻는 방법은 스페어 다음에 스트라이크가 나오는 것뿐이다. 따라서 기록과 맞는 경기는 아홉 가지다.

둘째 테스트 케이스에서는 ? 자리에 0부터 9까지 어느 숫자가 와도 기록과 맞는다.