TopCoder

User's AC Ratio

93.8% (30/32)

Submission's AC Ratio

54.3% (38/70)

Description

根據最新的生態學研究報導,在台北市植物園的蓮花池中,發現了一種奇特的海藻,此種海藻的外形具有一種十分特殊的性質:

1. 種子落地後,經過一天的時間,會先長出一根長一公分的綠色分枝。
2. 綠色的分枝,經過一天的時間後,會向上成長一公分,並且變成黃色。
3. 黃色的分枝,經過一天的時間後,會向上成長一公分,並且分成左右兩個分枝,其中左分枝為綠色,右分枝為黃色。
4. 所有的分枝都不會互相交錯,同時恰好成長在同一個平面上。

舉例來說,若我們由左而右俯視觀察此海藻每天的生長情形,則在種子落地後的第一天,觀察結果為『綠』,第二天的觀察結果為『黃』,第三天的觀察結果為『綠黃』,第四天的觀察結果為『黃綠黃』, 第五天的觀察結果為『綠黃黃綠黃』,依此類推。請寫一個程式,預測在第N天時,由左邊數來第K個分枝的顏色為何。

Input Format

輸入檔中的第一行有一個正整數M,代表此輸入檔中共有M組測試資料。
接下來的M行中,每一行代表其中一組測試資料,含有兩個以空白相間隔的正整數,分別依次為N與K。
為方便起見,所有的測試資料皆滿足0<M<10,0<N<100,且0<K<2,000,000,000。

Output Format

請根據輸入檔的資料,依序在每一行中,輸出第N天時,由左邊數來第K個分枝的顏色(請用數字0代表綠色,1代表黃色)。
若第N天時,此海藻的分枝數少於K,則輸出-1。

Sample Input

輸入檔範例 1
1
3 1

輸入檔範例 2
3
3 1
5 5
6 100

Sample Output

輸出檔範例 1
0

輸出檔範例 2
0
1
-1

Hints

Problem Source

原TIOJ1677 / 98北市賽(prob 1)

Subtasks

For Testdata: 0 ~ 0, Score: 20
For Testdata: 1 ~ 1, Score: 20
For Testdata: 2 ~ 2, Score: 20
For Testdata: 3 ~ 3, Score: 20
For Testdata: 4 ~ 4, Score: 20
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 262144
1 1000 65536 262144
2 1000 65536 262144
3 1000 65536 262144
4 1000 65536 262144