정지 판정 기계

정지 문제는 프로그램의 소스와 입력이 주어졌을 때 그 프로그램이 언젠가 끝나는지 아니면 영원히 돌아가는지를 판정하는 문제다. 앨런 튜링은 1936년에 모든 프로그램과 입력의 쌍을 판정하는 일반적인 알고리즘이 존재하지 않는다는 것을 증명했다. 그래서 임의의 프로그램을 받아 정지 여부를 알려주는 기계는 만들 수 없다. 그러나 언어를 충분히 좁히면 판정이 가능해진다. 아래에서 정의하는 언어 X가 그런 언어다.

언어 X로 쓴 프로그램은 goto 문 $N$개로만 이루어진다. 줄 번호는 $0$번부터 $N-1$번까지이고, 각 줄에는 goto 문이 정확히 하나 있다. goto 문의 형태는 다음과 같다.

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

이 문장은 조건 $c_i$가 참이면 $l_i$번 줄로 이동한다는 뜻이다 ($1 \le i \le k$). 조건 안에는 공백이 없고, 공백은 goto 키워드 뒤, 콜론 뒤, 쉼표 뒤에만 나온다.

조건은 서로 독립이고 어떤 입력에서는 참이 될 수 있다. 따라서 실행이 어떤 줄에 도달했을 때, 그 줄의 goto 문에 적힌 목표 중 어느 것으로든 이동할 수 있다. 실행은 $0$번 줄에서 시작한다. $N$번 줄에 도달하면 프로그램이 정지한다. 한 걸음은 goto 문 하나를 실행해 다른 줄로 옮겨가는 것을 뜻한다.

프로그램마다 정지하는지 판정하고, 어떤 조건 조합에서도 정지한다면 최악의 경우 걸음 수를 구한다.

첫째 줄에 테스트 케이스의 수 $T$가 주어진다 ($0 \le T \le 11$).

각 테스트 케이스는 프로그램 하나다. 테스트 케이스의 첫째 줄에는 프로그램의 줄 수 $N$이 주어진다 ($0 \le N \le 1000$). 이어지는 $N$개 줄에 goto 문이 한 줄에 하나씩 주어지며, 이 중 $i$번째 줄이 프로그램의 $i-1$번 줄이다.

goto 문 하나에는 목표가 $1$개 이상 $1000$개 이하 적혀 있고, 목표 줄 번호는 모두 $0$ 이상 $N$ 이하다. 같은 목표가 한 문장에 두 번 이상 나올 수도 있다.

각 테스트 케이스마다 최악의 경우 걸음 수를 한 줄에 출력한다. 조건이 어떻게 참이 되느냐에 따라 프로그램이 정지하지 않는 경우가 있다면, 걸음 수 대신 infinity를 따옴표 없이 출력한다.