볼링

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

볼링 규칙

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

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

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

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

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

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

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

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

첫 줄에 테스트 케이스의 개수 $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까지 어느 숫자가 와도 기록과 맞는다.