Amazing Elevator

Time Limit: 3 Seconds    Memory Limit: 65536 KB

Morteza lives in an apartment with 10 floors. The floors are numbered from 0 to 9 and the parking is located on floor 0. This apartment has an elevator with a seven-segment-display (SSD) in each floor that shows the location of the elevator. The parking SSD is amazing. Every day some random number of the segments become completely disabled.

One midnight, after parking his car in the parking, Morteza decided to use the elevator to reach his home. Initially, the elevator was on a floor which is called, from now on, as the initial location. During waiting in the parking, it becomes a kind of game for him to find the initial location of the elevator as soon as possible. He pushes the button of the elevator and watches SSD during changing the floors (we are sure that at this time there is not any other person that wants to use the elevator). Although some segments of SSD may be corrupted, but he can sense changes of the floor from the noises that the elevator makes. Help him to find the initial location of the elevator as soon as possible. In order to clear the problem, it should be underlined that, during this game Morteza is waiting in the parking and traces the elevator by watching SSD.

Input

The first line of the input is an integer n<=100 that shows the number of test cases. Each test case is presented in a separate line and started with the initial location of the elevator (0<=k<=9) followed by a binary string of size 7 (ABCDEFG). Each element of this string corresponds to a segment of the SSD according to the following image.

In this string 1 means the segment is healthy and 0 means it is completely disabled.

Output

For each test case, output the floor in which, Morteza becomes sure about the first location of the elevator in a separate line.

Sample Input

2
5 1111111
6 0101100

Sample Output

4
5
Submit

Source: 13th Iran Nationwide Internet Contest - Shiraz