Description

Input

Output

Sample Input

1
3 3 7
5 1 2 3 4 1
3 1 2 5
3 5 1 6
1 2
1 4
2 4
3 4
6 6
1 1
7 7

Sample Output

1
0
1
0
1
0
0

HINT

Source/Category