Description

有一种特别的计算机，它有 10 个寄存器和 1000 个字长的内存。每个寄存器和内存单元中都可以存储一个 3 位的整数（0~999）。这种计算机的指令都被编码为 3 位整数，并存储在内存中。指令编码后的含义如下： 100 终止 2dn 将寄存器 d 设定为 n（0~9之间） 3dn 把 n 与寄存器 d 中的值相加并存储在寄存器 d 中 4dn 把 n 与寄存器 d 中的值相乘并存储在寄存器 d 中 5ds 将寄存器 s 中的值赋给寄存器 d 6ds 将寄存器 s 中的值与寄存器 d 中的值相加并存储在寄存器 d 中 7ds 将寄存器 s 中的值与寄存器 d 中的值相乘并存储在寄存器 d 中 8da 将寄存器 a 所指的内存地址中的数据读取到寄存器 d 中 9sa 把寄存器 s 中的数据保存到寄存器 a 所指的内存地址中 0ds 如果寄存器 s 非零，就跳转到寄存器 d 所指的下标对应的命令去 开始时，所有的寄存器都是 000，而内存的数据则通过标准输入读入。该计算机从内存地址 0 开始执行，而每条指令执行的结果都要对 1000 取模。

Input

输入的第一行是一个正整数，它表示在输入中有多少组数据，每一组数据前都有一行空白。 每一组数据最多有 1000 条，它们表示内存中从地址 0 开始存储的数值。没有指定的内存中存储的数据都是 0。

Output

对于每一组数据，输出该计算机在执行过程中一共处理了多少条指令（包括终止指令），你可以假设程序最终一定会停止。在输出的每一组结果之间，都要增加一个空行。

Samples

2

299
492
495
399
492
495
399
283
279
689
078
100
000
000
000

456
789
234
453
125
175
183
256
012
100
000

16

7

Hint

注意0操作，是需要存下来所有命令，跳转的时候要到对应的命令去