You are given an undirected graph with n nodes and an integer m.

Find if it is possible to color all the vertices of the graph using atmost m colors, such that no two adjacent vertices have the same color.

Note: You are given the graph in the form of an adjacency matrix adjMatrix of size n*n.
adjMatrixij = 1 means there is an edge between nodes i and j.

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:

• Two space-separated integers 'n' and 'm' denoting the number of nodes and available colors.
• n lines, each containing n space-separated numbers making up the adjacency matrix.

Output Format

For each test case, the output has a line with 1 or 0, denoting if valid coloring is possible or not.

Sample Input

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

Expected Output

1
0
0

Constraints

1 <= T <= 10
1 <= n, m <= 20
0 <= adjMatrixij <= 1