Aaron and Bruce

Aaron is a vicious criminal. He has repeatedly committed crimes (2 shoplifting, 16 peeping, 256 underwear thieves, 65,536 escapes), but has continued to escape from the police with his extraordinary physical abilities. Bruce is a police officer. Although he does not have outstanding athletic ability, he enjoys photography and has the skill to publish his photographs in magazines.

One day Bruce came to take a picture in the mountains. Then I happened to find Aaron's hideout. As Bruce chased Aaron, who escaped, they fell into a pit and wandered into ancient ruins.

The ancient ruins consist of several rooms and passages connecting the rooms. When there are M rooms in the ancient ruins, the rooms in the ruins are numbered from 0 to M-1 respectively.

Aaron thought that it might expire while he was escaping, so he moved through the ruins so that he could continue to escape for the longest time when Bruce moved optimally. Bruce wants to photograph Aaron quickly, so he moves through the ruins so that Bruce can be photographed the fastest when Aaron moves optimally.

Aaron and Bruce act in turn. The first is Aaron's turn. In each turn, you can move to or stay in one of the adjacent rooms. When Aaron and Bruce enter the same room, Bruce shall photograph Aaron.

Find out how long it will take Bruce to shoot Aaron. Time is expressed in terms of the number of turns, and when both Aaron and Bruce have acted once, it is counted as one turn.

For example, in the situation shown in Fig. 5, if Aaron escapes to room 5, Bruce will reach it in 4 turns, but if Aaron escapes to room 7, Bruce will take 5 turns to reach it. For Aaron, the answer is 5 turns because he can escape for the longest time by escaping to room 7.

An example where Aaron can continue to escape for 5 turns.

Figure 5: An example where Aaron keeps escaping for 5 turns.

Also, in the situation shown in Fig. 6, Aaron can escape forever by moving the room away from Bruce.

An example of Aaron being able to escape forever.

Figure 6: An example of Aaron being able to escape forever.

Input

The first line of input is given the number N (0 <N ≤ 100), which represents the number of datasets. The next line is followed by N datasets.

Each dataset consists of the shape of ancient ruins and the initial positions of Aaron and Bruce. First, the number of rooms in the ancient ruins M (2 ≤ M ≤ 50) is given. Next, a matrix with the number of elements M × M is given. The element of each matrix is ​​0 or 1, and if the jth number in row i is 1, it means that room i and room j are connected by a passage (however, the row and column numbers of the matrix). Counts from 0). The values ​​of the (i, j) and (j, i) components of the matrix are always equal, and the value of the (i, i) component is 0. Then two integers a and b are given. Each integer indicates the room number at the initial position of Aaron (0 ≤ a <M) and the room number at the initial position of Bruce (0 ≤ b <M). The values ​​of a and b are always different.

Output

For each dataset, print in one line how many turns Bruce will take to shoot Aaron. If you can't shoot no matter how much, output " infinity ".

Example

Input

6 8 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 3 0 4 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 5 0 1 0 1 0 1 0 0 1 0 0 0 0 0 1 1 1 0 0 0 0 0 1 0 0 2 0 5 0 1 0 0 1 1 0 1 1 1 0 1 0 1 0 0 1 1 0 1 1 1 0 1 0 2 4 5 0 1 0 1 0 1 0 1 1 0 0 1 0 0 1 1 1 0 0 1 0 0 1 1 0 3 0 5 0 1 0 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 0 4

Output

5 infinity infinity 2 infinity 1

inputFormat

Input

The first line of input is given the number N (0 <N ≤ 100), which represents the number of datasets. The next line is followed by N datasets.

Each dataset consists of the shape of ancient ruins and the initial positions of Aaron and Bruce. First, the number of rooms in the ancient ruins M (2 ≤ M ≤ 50) is given. Next, a matrix with the number of elements M × M is given. The element of each matrix is ​​0 or 1, and if the jth number in row i is 1, it means that room i and room j are connected by a passage (however, the row and column numbers of the matrix). Counts from 0). The values ​​of the (i, j) and (j, i) components of the matrix are always equal, and the value of the (i, i) component is 0. Then two integers a and b are given. Each integer indicates the room number at the initial position of Aaron (0 ≤ a <M) and the room number at the initial position of Bruce (0 ≤ b <M). The values ​​of a and b are always different.

outputFormat

Output

For each dataset, print in one line how many turns Bruce will take to shoot Aaron. If you can't shoot no matter how much, output " infinity ".

Example

Input

6 8 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 3 0 4 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 5 0 1 0 1 0 1 0 0 1 0 0 0 0 0 1 1 1 0 0 0 0 0 1 0 0 2 0 5 0 1 0 0 1 1 0 1 1 1 0 1 0 1 0 0 1 1 0 1 1 1 0 1 0 2 4 5 0 1 0 1 0 1 0 1 1 0 0 1 0 0 1 1 1 0 0 1 0 0 1 1 0 3 0 5 0 1 0 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 0 4

Output

5 infinity infinity 2 infinity 1

样例

6
8
0 1 0 0 0 0 0 0
1 0 1 0 0 0 0 0
0 1 0 1 1 0 0 0
0 0 1 0 0 0 0 0
0 0 1 0 0 1 1 0
0 0 0 0 1 0 0 0
0 0 0 0 1 0 0 1
0 0 0 0 0 0 1 0
3 0
4
0 1 1 0
1 0 0 1
1 0 0 1
0 1 1 0
1 0
5
0 1 0 1 0
1 0 0 1 0
0 0 0 0 1
1 1 0 0 0
0 0 1 0 0
2 0
5
0 1 0 0 1
1 0 1 1 1
0 1 0 1 0
0 1 1 0 1
1 1 0 1 0
2 4
5
0 1 0 1 0
1 0 1 1 0
0 1 0 0 1
1 1 0 0 1
0 0 1 1 0
3 0
5
0 1 0 1 1
1 0 1 0 1
0 1 0 1 0
1 0 1 0 1
1 1 0 1 0
0 4

5
infinity
infinity
2
infinity
1

</p>