Halting Machine

Time limit2sMemory limit512 MB

Summary

Parse N goto statements, build a directed graph, and print the longest path length from line 0 to line N, or infinity if a cycle is reachable on some path to N.

Level: Medium6 of 10
Topics: Graph, Dynamic programming, Topological sort, Implementation
Solved: No attempts yet

Problem

The halting problem asks whether a program, given its source and its input, eventually finishes or runs forever. Alan Turing proved in 1936 that no general algorithm decides this for every pair of a program and an input, so a machine that takes an arbitrary program and reports whether it halts cannot exist. Restrict the language enough and the question becomes decidable. Language X, defined below, is such a language.

A program in language X consists of $N$ goto statements and nothing else. Lines are numbered $0$ through $N-1$ , and every line holds exactly one goto statement. A goto statement looks like this.

goto l1: c1, l2: c2, ..., lk: ck;

The statement moves execution to line $l_i$ when condition $c_i$ is true ( $1 \le i \le k$ ). Conditions contain no spaces, and a space appears only after the goto keyword, after a colon, and after a comma.

The conditions are independent and each one is true for some input. So whenever execution reaches a line, it can move to any of the targets listed in that line's goto statement. Execution starts at line $0$ . The program halts when execution reaches line $N$ . One step is the execution of one goto statement, which moves to another line.

For each program, decide whether it halts, and when it halts under every combination of conditions, report the number of steps in the worst case.

Input

The first line contains the number of test cases $T$ ( $0 \le T \le 11$ ).

Each test case is one program. The first line of a test case contains the number of lines $N$ in the program ( $0 \le N \le 1000$ ). The next $N$ lines each contain one goto statement, and the $i$ th of those lines is line $i-1$ of the program.

One goto statement lists at least $1$ and at most $1000$ targets, and every target line number is at least $0$ and at most $N$ . The same target can appear more than once in one statement.

Output

For each test case, print the number of steps in the worst case on its own line. If some way of making the conditions true leaves the program running forever, print infinity without quotes instead of a step count.

Examples2

Example 1

Input

2
2
goto 1: a>b;
goto 0: 10<x;
3
goto 2: a<b, 1: b<a;
goto 3: a>0;
goto 1: b>0;

Expected output

infinity
3

Example 2

Input

3
0
1
goto 1: x>0;
1
goto 0: x>0;

Expected output

0
1
infinity