"I read somewhere that everybody on this planet is separated by only six other people. Six degrees of separation between us and everyone else on this planet. The President of the United States, a gondolier in Venice, just fill in the names. I find it A) extremely comforting that we're so close, and B) like Chinese water torture that we're so close because you have to find the right six people to make the right connection... I am bound to everyone on this planet by a trail of six people." - Ouisa Kitteridge, "Six Degrees of Separation"

Is widely know that one is separated from everyone in the world in no more than 6 degrees of separation. A degree of separation is defined by the minimum numbers of connections you need to make to contact someone else. For instance, if you know personally another person, then you are separated by one degree. If you know somebody through some friend but not directly (a friend of a friend), then you are separated by two degrees, and so on.

Nevertheless, young Kevin Smith is not convinced about this theory and wants to probe it false. To achieve this, he has hacked the Hi6! social network and requested you to help him knock down the theory of six degrees of separation.

Input

The first line contains an integer T, which specifies the number of test cases. Then, T test case descriptions will follow. Each test case will start with a line with one positive integer, N meaning the number of connections. The next N lines will contain the following pattern:

<name_1> <name_2>

meaning that person "<name_1>" is connected with the person "<name_2>" by making D connections and vice versa. Note that both persons can know each other by a lower degree of separation using other connections.

Output

For each input case you must print the string "Case #i: ", where i is the test case number, starting from 1, following by the maximum degree of separation between the specified people. If there is someone that cannot connect to another person, print "INFINITE" instead.

Constraints

• All names will be non-empty strings composed only by lowercase characters.
• All names will have between 1 and 10 characters, inclusive.
• "<name_1>" will be different than "<name_2>" for all connections.
• There will be no pair of connections between the same pair of persons.
• D will be an integer between 1 and 1000, inclusive, for all connections.
• T will be between 1 and 100, inclusive.
• N will be between 1 and 10^5, inclusive.

Example

Input:
3
2
john judy 1
mary peter 1
3
john judy 7
john peter 2
judy peter 2
7
john judy 3
katie peter 4
john peter 2
judy mary 1
peter mary 2
john katie 1
katie mary 1

Output:
Case #1: INFINITE
Case #2: 4
Case #3: 3