Guess the Birthday

Time limit2sMemory limit1024 MB

Summary

Given the digits in Chanwoo's ID, count the calendar dates in a leap year whose month and day share no digits with those ID digits.

Level: Easy3 of 10
Topics: Brute force, Bit manipulation
Solved: No attempts yet

Problem

Many people include numbers related to their birthday in their ID, but the numbers that appear in Chanwoo's ID share no digits with the digits of his birth month or birth day. Given the numbers that appear in Chanwoo's ID, find how many dates could be Chanwoo's birthday.

Chanwoo was born in a leap year, so February 29 is a possible birthday. If the month or day has one digit, its tens place is treated as blank. So for June 7, the birthday contains no 0, while June 10 or October 7 contains a 0.

Input

The first line contains the number of test cases $T$ . $(1 \le T \le 1\,234)$

Each of the next $T$ lines contains 10 integers separated by spaces, one test case per line. If the digit $i-1$ appears in Chanwoo's ID, the $i$ -th integer is $1$ . Otherwise it is $0$ . $(1 \le i \le 10)$

Output

Print the answer for each test case on its own line.

Examples2

Example 1

Input

4
1 1 1 1 1 0 0 0 0 0
0 0 0 0 0 1 1 1 1 1
0 1 0 1 0 1 0 1 0 1
1 0 0 0 0 0 0 0 0 0

Expected output

Example 2
Input
```
1
1 1 1 1 1 1 0 0 1 1
```
Expected output
```
4
```