Hang or not to hang

Time Limit: 1 Second    Memory Limit: 32768 KB

Little Tom is learning how to program. He has just written some programs but is afraid to run them, because he does not know if they will ever stop. Please write a program to help him.

This task is not as easy as it may seem, because Tom's programs may behave nondeterministically.

Given a program written by Tom, your program should tell him whether his program can stop and if so, what is the shortest possible time before it stops.

Tom's computer consists of 32 1-bit registers and the program consists of N instructions. The registers are numbered from 0 to 31 and the instructions are numbered from 0 to N-1.

Below, MEM[a] stands for the contents of the a-th register, 0 <= a, b < 32, 0 <= x < N, 0 <= c <= 1.

The instruction set is as follows:

Instruction	Semantics
AND a b OR a b XOR a b NOT a MOV a b SET a c RANDOM a JMP x JZ x a STOP	MEM[a] := MEM[a] and MEM[b] MEM[a] := MEM[a] or MEM[b] MEM[a] := MEM[a] xor MEM[b] MEM[a] := not MEM[a] MEM[a] := MEM[b] MEM[a] := c MEM[a] := random value (0 or 1) jump to the instruction with the number x jump to the instruction with the number x if MEM[a] = 0 stop the program

The last instruction of every program is always STOP (although there can be more than one STOP instruction in a program). Every program starts with the instruction number 0. Before the start, the contents of the registers can be arbitrary values. Each instruction (including STOP) takes 1 processor cycle to execute.

Task

Write a program that:

• reads the program,
• computes the shortest possible running time of the program,
• writes the result.

Input

The input consists of several test cases.
For each case, the first line contains an integer N (1 <= N <= 16) being the number of instructions of the program. Each of the next N lines contains one instruction of the program in the format given above. You may assume that the only white characters in the program are single spaces between successive tokens of each instruction.

Output

For each test case, print in one line the shortest possible running time of the program, measured in processor cycle. If the program cannot stop, print the word HANGS.

Sample Input

5
SET 0 1
JZ 4 0
RANDOM 0
JMP 1
STOP
5
MOV 3 5
NOT 3
AND 3 5
JZ 0 3
STOP

Sample Output

6
HANGS

Submit

Source: Central Europe 2003