{{{~cpp
#include <iostream>
#include <stdlib.h>
#include <stdio.h>
using namespace std;

int regist[10], ram[1000];
char temp[4];
int testcase, number;
int i, counting;
int nResult;
int a, b, c;

int process()
{
	nResult=0;
	counting =0;
	for(i=0; i<10; i++)
		regist[i] = 0;
	while(ram[counting]!=100)
	{
		a = ram[counting]/100;;
		b = (ram[counting]/10)%10;
		c = ram[counting]%10;
		counting++;
		
		if(a==2)
			regist[b] = c;
		else if(a==3)
			regist[b] = (regist[b] + c)%1000;
		else if(a==4)
			regist[b] = (regist[b] * c)%1000;
		else if(a==5)
			regist[b] = regist[c];
		else if(a==6)
			regist[b] = (regist[b] + regist[c])%1000;
		else if(a==7)
			regist[b] = (regist[b] * regist[c])%1000;
		else if(a==8)
			regist[b]= ram[regist[c]];
		else if(a==9)
			ram[regist[c]] =regist[b];
		else if(a==0)
		{
			if(regist[c]!=0)
				counting = regist[b];
		}
		nResult++;
	}
	return nResult+1;
}

int main()
{
	cin >> testcase;
	cin.getline(temp, 4);
	cin.getline(temp, 4);
	while(testcase--)
	{
		for(number=0; cin.getline(temp, 4) && *temp; number++) 
			sscanf(temp, "%d", &ram[number]);
		for(number; number<1000; number++)
			ram[number]=0;
		cout << process() << endl;
		if(testcase!=0)
			cout << endl;
	}
	return 0;
}
}}}