TopCoder

User's AC Ratio

66.7% (2/3)

Submission's AC Ratio

18.2% (2/11)

Tags

Description

『孫中山,原名孫文(1866年11月12日-1925年3月12日),字載之,號日新、逸仙,譜名德明,幼名帝象,
    是醫師、近代中國的民主革命家、中國國民黨總理、第一任中華民國臨時大總統、亦為中華民國國父。
        孫文流亡日本時,曾有一個廣為人知的化名「中山樵」,故後人慣以「中山先生」相稱;其後此稱謂便逐漸演化為「孫中山」。』

為了紀念偉大的國父,曉癸在後院養了一隻觸手。

這種觸手的末稍會寫著「中」或「山」,當然,觸手是會生長的,所以一條長著「中」的觸手隔天會變成長著「山」的觸手,長著「山」的觸手,隔天會分支出一條長著「中」的觸手跟一條「山」的觸手(一左一右)。這隻觸手剛買回來時是一隻只有一條長著「中」的觸手。

畢竟,觸手是糟糕的,所以當兩個長著「山」的觸手相鄰時,會纏在一起,看起來就跟一根觸手差不多(只是長得有點噁心),但不影響隔天的變化,也就是說,纏在一起的觸手,隔天會變成「中山中山」的樣子。

像這樣:
第一天 - 中
第二天 - 山
第三天 - 中山
第四天 - 山中山
第五天 - 中(纏在一起的觸手)中山

曉癸相當好奇,如果我們把每個觸手的末稍由左到右編號,如何知道在任意天數時,任意編號的觸手是什麼樣子呢(編號從0開始,且纏在一起的觸手算一個編號)?

為了方便,我們把「中」當作1,「山」當作2,纏在一起的觸手則是3。

Input Format

第一行有個數T (T<20000),代表有T筆測資。

接下來有T行,每行有兩個正整數a和b,代表第a天時編號b的觸手,a和b都不超過int32範圍。

觸手的編號由 1 開始。

Output Format

對每筆測資各輸出一個數(1,2,3),代表在第a天時編號b的觸手之狀態。

如果該觸手不存在,請輸出-1。

Sample Input 1

1
1 1

Sample Output 1

1

Hints

Problem Source

原TIOJ1593 / Problem Setter: butterfly21

Subtasks

No. Testdata Range Score
1 0 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1