#include<cstdio>

#include<iostream>

#include<string>

#include<algorithm>

#include<iterator>

#include<cstring>

//uva 10033 Problem G: Interpreter

#define ONLINE_JUDGE

using namespace std;

int regs[10];

int ram[1000];

int steps;

int pc=0;

int oper, arg1, arg2;

void load_ram()

{

    steps=0;

    pc=0;

    memset(regs, 0 ,sizeof(regs));

    memset(ram, 0 ,sizeof(ram));

    //string s;

    char s[5];

    int i=0;

    //for(int i=0;getline(cin, s)&&s.length();i++)

    for(int i=0;fgets(s, sizeof(s), stdin);i++)

    {

        if(s[0]=='\n')

        {

 //           printf("\\n \n");

            break;

        }

        //ram[i]=atoi(s.c_str());

        ram[i]=atoi(s);

#ifndef ONLINE_JUDGE

        cout<<ram[i]<<endl;

#endif

    }

}

void decode()

{

    oper=ram[pc]/100;

    arg1=ram[pc]/10%10;

    arg2=ram[pc]%10;

    pc++;

    steps++;

#ifndef ONLINE_JUDGE

    printf("steps %d pc %d: %d %d %d\n", steps, pc-1, oper, arg1, arg2);

#endif

}

void run()

{

    while(1)

    {

        decode();

        switch(oper)

        {

            //halt

            case 1:

                goto END;

                break;

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

            case 2:

                regs[arg1]=arg2;

                break;

            //3dn means add n to register d

            case 3:

                regs[arg1]+=arg2;

                regs[arg1]%=1000;

                break;

            //4dn means multiply register d by n

            case 4:

                regs[arg1]*=arg2;

                regs[arg1]%=1000;

                break;

            //5ds means set register d to the value of register s

            case 5:

                regs[arg1]=regs[arg2];

                break;

            //6ds means add the value of register s to register d

            case 6:

                regs[arg1]+=regs[arg2];

                regs[arg1]%=1000;

                break;

            //7ds means multiply register d by the value of register s

            case 7:

                regs[arg1]*=regs[arg2];

                regs[arg1]%=1000;

                break;

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

            case 8:

                regs[arg1]=ram[regs[arg2]];

                break;

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

            case 9:

                ram[regs[arg2]]=regs[arg1];

                break;

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

            case 0:

                if(regs[arg2]!=0)

                    pc=regs[arg1];

                break;

            default:

                break;

        }

    }

END:

    return;

}

int main()

{

    int n;

    bool first=true;

    char instr[5]={0};

    //cin>>n;

    scanf("%d", &n);

    //ignore \n

    //cin.ignore();

    fgets(instr, sizeof(instr), stdin);

    memset(instr, 0, sizeof(instr));

    //ignore a line

    //cin.ignore(1024, '\n');

    fgets(instr, sizeof(instr), stdin);

    while(n-- >0)

    {

        load_ram();

        run();

        if(!first)

            printf("\n");

        printf("%d\n", steps);

        first=false;

    }

    return 0;

}