TopCoder

赤ずきんチャチャ
もっと心の中を二人見せ合えたなら 答えはつかめるよ

User's AC Ratio

75.0% (6/8)

Submission's AC Ratio

22.2% (8/36)

Tags

Description

你成功的讓所有的殭屍都變成了行動緩慢的J殭屍後,便帶著你身旁的小蘿莉逃走了。
終於甩開了後面的殭屍群,你便和你身邊的蘿莉坐著休息。
「你叫什麼名字啊?」依照攻略女主角的第一步,你這麼問到。「我叫...我叫...祈(Inori)」
「啊啊!真是好聽的名子阿,我叫...糟了!」此時你發現剛剛以為已經甩開的殭屍群都追了上來了。此時前方的路徑是一座奇怪的木橋。
「我們趕快過橋吧」,正當你要踏上木橋的第二塊木板上時,木板竟然自己跑走了,你差點就踩空而掉下去。
「喔膩醬,這個木板上面寫了什麼?」
你看了下那在橋旁的木板,原來這是一座有機關的橋,上面寫著:
哈哈哈!歡迎來到梗賤橋!這是由我精心設計的機關橋。這上面的木板是會移動的,或許你早就已經因此掉入下面的18層地獄在喝孟婆湯了哈哈哈...唔..好像沒什麼梗。
好吧,讓我大發慈被的告訴你們這個木板交換的規則吧,這座橋有N塊木板,開始木板的編號分別是1∼N
現在選出1∼N的質數
從2開始,2的倍數的木板便會作以下交換:4號變到2號的位置,6號變到4號的位置,……,而編號為2的木板會變到編號為最後一個2的倍數的木板的位置
然後接下來換3,3的倍數的木板便會作以下交換:6號變到3號的位置,9號變到6號的位置,……,而編號為3的木板會變到編號為最後一個3的倍數的木板的位置
一直做下去,直到1∼N的質數都操作過了為止。

比如當N=10,原本木板的序列為1 2 3 4 5 6 7 8 9 10
當2的倍數操作完 1 4 3 6 5 8 7 10 9 2
當3的倍數操作完 1 4 6 9 5 8 7 10 3 2
當5的倍數操作完 1 4 6 9 10 8 7 5 3 2
當7的倍數操作完 1 4 6 9 10 8 7 5 3 2

所以最後木板的序列即是1,4,6,9,10,8,7,5,3,2

嘻嘻嘻!還要跟你提醒一點,所有編號為質數的木板都設了陷阱,只要一踩下去就,嘻嘻嘻嘻...

當你讀完了木板上的敘述後,眼前橋的木板似乎都已經換完了而成了最終木板的序列。

給你N值和詢問第M個木板,請判斷他是否是安全的,好通過這座橋吧!

Input Format

輸入第一行為數字T,有T組詢問要判斷。
接下來T行,每行2個數字N,M。

Output Format

輸出T行,每行一個數字,代表有N個木板的橋經過木板交換的過程後位置第M的木板原本的編號是多少。
如果這個木板是質數(被設陷阱的木板)
那只需要輸出"Geng Jian malheureux roi mauvaise!!"提醒自己不要踩就可以了

Sample Input 1

2
10 4
10 9

Sample Output 1

9
Geng Jian malheureux roi mauvaise!!

Hints

測資組A : N≤10,T≤5
測資組B : N≤1000,T≤10
測資組C : N≤106 ,T≤100
測資組D : N≤106 ,T≤106

Problem Source

Subtasks

No. Testdata Range Score
1 0~1 10
2 2~3 20
3 4~6 30
4 7~9 40

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 1
2 1000 65536 262144 2
3 1000 65536 262144 2
4 1000 65536 262144 3
5 1000 65536 262144 3
6 1000 65536 262144 3
7 1000 65536 262144 4
8 1000 65536 262144 4
9 1000 65536 262144 4