Interpreter

A certain computer has $10$ registers and $1000$ words of RAM. Each register or RAM location holds a $3$-digit integer between $0$ and $999$. Instructions are encoded as $3$-digit integers and stored in RAM. The encodings are as follows:

  • $1xy$ means halt (regardless of the values of $x$ and $y$)

  • $2dn$ means set register $d$ to $n$ (between $0$ and $9$)

  • $3dn$ means add $n$ to register $d$

  • $4dn$ means multiply register $d$ by $n$

  • $5ds$ means set register $d$ to the value of register $s$

  • $6ds$ means add the value of register $s$ to register $d$

  • $7ds$ means multiply register $d$ by the value of register $s$

  • $8da$ means set register $d$ to the value in RAM whose address is in register $a$

  • $9sa$ means set the value in RAM whose address is in register $a$ to the value of register $s$

  • $0ds$ means goto the location in register $d$ unless register $s$ contains $0$

All registers initially contain $000$. The first instruction to be executed is at RAM address $0$. All results of add/multiply instructions are reduced modulo $1000$.

Input

The initial content of the RAM is read from standard input. The input to your program consists of up to $1000$ $3$-digit unsigned integers, representing the contents of consecutive RAM locations starting at $0$. Unspecified RAM locations are initialized to $000$.

Output

The output from your program is a single integer: the number of instructions executed up to and including the halt instruction. You may assume that the program does halt and takes at most $10\, 000$ steps.

Sample Input 1 Sample Output 1
299
492
495
399
492
495
399
283
279
689
078
100
000
000
000
16