Byteasar yêu thích cả bowling lẫn thống kê. Anh đã ghi lại kết quả của một số ván bowling trước đây. Thật không may, một số ký tự trong các ghi chép đã bị nhòe và không thể đọc được. Byteasar nhờ bạn viết chương trình tính số ván đấu khác nhau phù hợp với các ghi chép của anh.

Luật bowling

Một ván bowling gồm \(n\) lượt: \(n-1\) lượt thường và một lượt cuối. Trong một ván đấu thông thường, \(n=10\). Khi bắt đầu mỗi lượt, \(10\) ki được dựng thẳng ở cuối đường băng; người chơi được ném bóng tối đa hai lần, hoặc ba lần đối với lượt cuối, để cố gắng làm đổ càng nhiều ki càng tốt. Mỗi lượt được biểu diễn bằng hai ký tự nếu là lượt thường, hoặc ba ký tự nếu là lượt cuối.

Với mỗi lần ném, người chơi nhận được số điểm cơ bản bằng số ki bị làm đổ trong lần ném đó. Điểm cơ bản của một lượt là tổng điểm cơ bản của các lần ném trong lượt. Nếu làm đổ cả \(10\) ki trong một lượt thường, tức là đạt \(10\) điểm cơ bản, người chơi còn được nhận điểm thưởng.

Các quy tắc cho một lượt thường như sau:

• Nếu làm đổ cả \(10\) ki ngay trong lần ném đầu tiên, người chơi đạt một strike và lượt đó kết thúc. Điểm thưởng là tổng điểm cơ bản của hai lần ném tiếp theo. Một strike được ký hiệu là x-.
• Nếu cần cả hai lần ném để làm đổ hết \(10\) ki, người chơi đạt một spare. Điểm thưởng là điểm cơ bản của lần ném tiếp theo. Một spare được ký hiệu là A/, trong đó A là chữ số chỉ số ki bị làm đổ ở lần ném đầu tiên của lượt.
• Nếu sau cả hai lần ném chỉ có nhiều nhất \(9\) ki bị làm đổ, người chơi chỉ nhận điểm cơ bản. Lượt này được ký hiệu là AB, trong đó A và B lần lượt là các chữ số chỉ số ki bị làm đổ trong lần ném thứ nhất và thứ hai, với \(A+B<10\).

Điểm thưởng được cộng vào điểm của lượt đạt strike hoặc spare, mặc dù số điểm thưởng cụ thể phụ thuộc vào những lần ném trong các lượt sau.

Đối với lượt cuối, ban đầu người chơi được ném hai lần. Nếu sau hai lần ném chỉ có nhiều nhất \(9\) ki bị làm đổ, lượt đó kết thúc. Ngược lại, nếu hai lần ném đầu tạo thành một spare hoặc lần ném đầu là một strike, người chơi được ném lần thứ ba. Mỗi khi làm đổ hết số ki đang đứng trong bất kỳ lần ném nào, các ki được dựng lại như ban đầu cho lần ném tiếp theo. Điểm của lượt cuối là tổng số ki bị làm đổ; các strike và spare trong lượt này không mang lại điểm thưởng.

Có bảy dạng biểu diễn lượt cuối, trong đó A và B là các chữ số:

• xxx: ba strike liên tiếp; được \(30\) điểm.
• xxA: hai strike liên tiếp, sau đó làm đổ \(A\) ki; được \(20+A\) điểm.
• xA/: một strike, sau đó là một spare với \(A\) ki bị làm đổ ở lần ném đầu của spare; được \(20\) điểm.
• xAB: một strike, sau đó là hai lần ném làm đổ lần lượt \(A\) và \(B\) ki, với \(A+B<10\); được \(10+A+B\) điểm.
• A/x: một spare với \(A\) ki bị làm đổ ở lần ném đầu, sau đó là một strike; được \(20\) điểm.
• A/B: một spare với \(A\) ki bị làm đổ ở lần ném đầu, sau đó làm đổ \(B\) ki ở lần ném cuối; được \(10+B\) điểm.
• AB-: hai lần ném làm đổ lần lượt \(A\) và \(B\) ki, với \(A+B<10\); được \(A+B\) điểm.

Mỗi ván đấu được mô tả bằng một xâu gồm \(2n+1\) ký tự. Khi ván đấu kết thúc, có thể tính tổng điểm tích lũy sau từng lượt.

Dữ liệu vào

Dòng đầu chứa số nguyên \(q\) (\(1\le q\le25\)), là số trường hợp cần xét. Tiếp theo là \(3q\) dòng; mỗi trường hợp được mô tả bằng ba dòng:

• Dòng thứ nhất chứa số nguyên \(n\) (\(2\le n\le10\)), là số lượt.
• Dòng thứ hai chứa xâu gồm \(2n+1\) ký tự mô tả ván đấu trong ghi chép của Byteasar. Mỗi ký tự bị nhòe được thay bằng ?.
• Dòng thứ ba chứa \(n\) số nguyên cách nhau bởi dấu cách, là tổng điểm tích lũy sau từng lượt. Với mỗi số, hoặc tất cả các chữ số đều đọc được, hoặc tất cả đều bị nhòe. Số bị nhòe hoàn toàn được thay bằng -1.

Dữ liệu ra

In \(q\) dòng, mỗi dòng ứng với một trường hợp theo đúng thứ tự đầu vào. Trên mỗi dòng, in một số nguyên là số ván đấu khác nhau phù hợp với trường hợp đó.

Hai ván đấu được coi là khác nhau khi và chỉ khi chúng khác nhau ở ít nhất một lần ném, tức là hai xâu mô tả gồm \(2n+1\) ký tự của chúng khác nhau. Dữ liệu bảo đảm mỗi trường hợp có ít nhất một ván đấu phù hợp và kết quả biểu diễn được bằng số nguyên có dấu \(64\) bit.

Phân nhóm

Các điều kiện dưới đây áp dụng cho từng trường hợp trong một bộ dữ liệu.

1. 16 điểm: xâu đầu vào có nhiều nhất sáu ký tự ?.
2. 17 điểm: kết quả không vượt quá \(10^9\).
3. 26 điểm: không có ván đấu nào phù hợp với dữ liệu vào mà xâu mô tả chứa ký tự x hoặc /.
4. 23 điểm: xâu đầu vào kết thúc bằng 00-, tức là người chơi được \(0\) điểm ở lượt cuối; đồng thời \(\min(3,n)\) số cuối cùng trên dòng thứ ba của trường hợp đó đều bằng -1.
5. 18 điểm: không có ràng buộc bổ sung.

Ví dụ

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

25
2
0000-
0 0
2
0000?
-1 -1
2
?0?0?
-1 -1
2
??12?
-1 -1
2
????/
-1 25
2
????x
-1 25
2
????-
-1 21
2
????0
-1 -1
2
??0?0
-1 -1
2
12?x?
-1 -1
2
34?/2
-1 -1
2
11?9?
-1 -1
2
x-?0-
-1 14
2
x-???
10 -1
2
x-???
-1 60
2
x-?0-
-1 -1
2
3/?/?
15 -1
2
00???
0 -1
2
?????
-1 -1
2
??x??
2 -1
2
x-??-
-1 26
2
?????
1 -1
2
?/???
10 -1
2
0???0
-1 -1
2
0???0
11 -1

1
1
210
66
60
60
40
1386
66
11
10
3
1
1
1
10
11
241
15906
228
9
482
210
231
1