10033 - Interpreter

某一個指令集架構有10個暫存器，記憶體大小有1000個字組，每一個暫存器的寬度及每一個記憶體位址都佔有3個十進位數字寬，足以表示0~999。每一個指令被編成3位數字的機器語言儲存在記憶體中，機器語言的編碼如下：

• 100 中止程式。
• 2dn 設定暫存器 d 的值為常數 n (n=0~9)。(d代表destination，表示最終運算的結果會回存到 d 上，以下的d都具有相同的意思)
• 3dn 暫存器 d 的值被加上常數 n。
• 4dn 暫存器 d 的值被乘上常數 n 。
• 5ds 設定暫存器 d 的值為暫存器 s 的值。
• 6ds 暫存器 d 的值被加上暫存器 s 的值。
• 7ds 暫存器 d 的值被乘上暫存器 s 的值。
• 8da 從記憶體位址取值儲存到暫存器 d ，該記憶體位置被儲存在暫存器 a 內。
• 9sa 把暫存器 s 的值存回記憶體，記憶體位置被儲存在暫存器 a 中。
• 0ds 分支運算，若暫存器 s 的值不為 0 則做分支跳躍(jump)，跳躍的位址由暫存器 d 所指定。

所有暫存器的初始值為000，而記憶體的初始值則從輸入中讀取，程式從位置0開始被執行，所有運算結果若發生溢位則取餘數。

Input

輸入的第一列為一個整數，表示有幾組測試資料，每組測試資料請見下一段說明。每組測試資料之前都用一個空行隔開。

每組測試資料最多會有1000個以3位數字表示的機器語言指令，所有指令會從0開始儲存在記憶體中，未指定內容的記憶體空間則初始化為000。

Output

每組測試資料的輸出請參考下一段的說明。每組輸出請用一個空行隔開。

每一組測試資料請輸出一個整數，表示總有多少指令被執行(包含最後的中止指令)，你可以假定程式最後會中止。

Sample Input

1

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

Sample Output

16

原文出處

感謝David Kuo堪誤