G :: BEATBIT

Time Limit: 2 Seconds    Memory Limit: 32768 KB

A software company is very much concerned that its software engineers do not write equivalent procedures into the new version of its main product BEATBIT. The BEATBIT system is written in the assembly language BITE, recently introduced by MacroSoft, in its .DOTFramework. So far, no one has invented a more powerful language to program complex digital circuits. The BITE assembly language operates on a stack ofbits, and is defined by the following four kinds of instructions:

label BRTRUE destlabel

Pops a bit from the top of the stack, and tests it. If the value is 1 continues execution at the instruction with label destlabel. If the value is 0 continues at the next program instruction.

label JMP destlabel

Continues execution at the instruction with label destlabel.

label RET1

Stops execution and returns 1.

label RET0

Stops execution and returns 0.

Here, label and destlabel are positive integers. A n-ary procedure of BITE is a sequence of instructions that expects N bit values on the stack as input, and produces one bit value, as the result of a RET0 or RET1 instruction. The instructions in the sequence are always labelled in increasing label sequence, and it is known that, for every possible input, the procedures always terminate. The program starts at the instruction with the lowest label.

Write a program that checks whether two BITE procedures compute the same boolean function for any sequence of the values, stored in the stack, provided as input.

Input

A positive integer P in a single line followed by a sequence of P pairs of BITE procedures. Each pair of BITE procedures is preceded by the number of bits expected in the stack (the arity of the procedures), represented by a positive integer, not greater than 128, in a single line. Next, for each BITE procedure there is a sequence of lines, each one containing a BITE instruction, and terminated by a single line containing END. Programs do not have more than 10,000 lines of code.

Output

A sequence of lines, the i-th line containing either 1 or 0 depending on whether the i-th pair of BITE procedures in the input compute the same boolean function or not.

Sample Input

2
2
10 BRTRUE 30
20 RET0
30 BRTRUE 50
40 RET0
50 RET1
END
20 BRTRUE 50
30 BRTRUE 40
40 RET0
50 BRTRUE 70
60 JMP 40
70 RET1
END
1
10 BRTRUE 30
20 RET0
30 RET1
END
50 RET0
END

Sample Output

1
0

Submit