Given a directed graph, find if it has any cycle?
A graph is cyclic, if you can start at a node in the graph, traverse along its edges, and return to the same initial node.

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

Return if it is cyclic or not.

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, depending on whether the graph is cyclic or not.

Sample Input

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

Expected Output

0
0
1
1

Constraints

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