Problem J
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.

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

16