Given a graph find if a path exists from the first node to the last node.

The graph has n nodes indexed 0 to n-1. It is given in the form of an adjacency list.

Find if a path exists from node 0 to node n-1.

Example

Testing

Input Format

The first line contains an integer T denoting the number of test cases.

For each test case, the input has the following lines:

• The first line contains the integer n.
• The next n lines descibes the adjacent nodes for the i^th node.
  • The first integer m denotes the number of adjacent nodes.
  • The next m integers denote adjacent nodes.

Output Format

For each test case, the output has one line with 1 or 0, denoting if a path exists.

Sample Input

4
4
1 1
2 2 0
2 0 3
1 1
4
1 1
1 0
3 0 1 3
1 1
2
1 0
1 1
2
2 0 1
0

Expected Output

1
0
0
1

Constraints

1 <= T <= 40
1 <= n <= 500
0 <= m <= n