Happy New Year 11111011110 | Online Programming Contest

You are quite new to Bioinformatics studies. While working in the lab you have met Professor Shakil, who is a bit crazy. You know that there are twenty-two chromosomes and there is the X chromosome and the Y chromosome.

Now Professor Shakil is very determined that there are mutants hiding among us (After watching the new Wolverine movie he went nuts). And he is very positive about a new type of chromosome, which is the I chromosome.

As the Professor is very excited and not suitable for lab work, he will give you a chromosome each time. You have to determine which type it is (X, Y, I or NotValid).

Chromosomes can be viewed as a set of nodes and edges. Look at the images for details. The dotted line represents that there can be an arbitrary number of nodes and edges in these directions (they have to represent a straight line, though).

Input

In the first line, you will be given the number of test cases T, where T <= 200. Then the test cases will follow. Each test case will have two integers at the beginning, N and M. Here N is the number of nodes and M is the number of edges, where 4 <= N <= 500 and 3 <= M <= (N * N - 1) / 2. Then M lines will follow, each consisting of two integers, U and V, which specifies that there is an edge between node U and node V. It is guaranteed that and given graph will be connected and there will be at most one edge between two nodes.

Output

You have to output the correct chromosome each test case represents, or NotValid if the test case doesn’t represent the three given chromosomes. You have to print “Case T: Z”, (without the braces) for each test case, where T is the test case number and Z is the correct chromosome or “NotValid”. Please look at the sample I/O for details.

Sample

Input:
2
4 4
1 2
2 3
3 4
4 1
4 3
1 2
2 3
2 4

Output:
Case 1: NotValid
Case 2: Y

Problem Setter: Nafis Ahmed, Special Thanks: Nafis Sadique