Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Trick or Trees

Limits: 1s, 512 MB · Custom Checker

One day, Raju was out roaming in the woods,when he suddenly stumbled upon a large garden. There were infinitely many trees in the garden of ages 1 to n (their ages were always integer values), and Raju soon found out that there were at least two trees having age i, for all integers i where 1<=i<=n.

The roots of the trees were entangled in such a way that if Raju picked up two trees with ages a1 and a2, a sequence of trees with ages a1, a2, a3, a4, ….. , ak would subsequently be uprooted, where ai= ai-2 (mod ai-1 ), for i>=3. Notice that there are no trees of age 0, so if ai-2 (mod ai-1 )=0, no tree will be further uprooted and the sequence will stop there. The sequence also stops if a tree of age m is uprooted (even if a1=m or a2=m).

The trees bear tasty ‘toklets’ as soon as they grow up, so Raju wants to take as many trees as he can with him and plant them in his own backyard. However, trees having age below m are too young and tender to be plucked. He wants to manually pluck only two trees and take all trees subsequently unplucked with him back home.

Raju wants your help to determine the ages of those two trees, so that the number of trees subsequently uprooted is maximized, and no tree of age less than m is plucked.

Input

The input starts with the number of test cases T (<100).

Each test case is represented by a single integer having two space separated integers n and m, where (1<=n<=10^12 , 1<=m<=n).

Output

For each test case, output two space separated integers a1 and a2 , in a single line, where a1 is the age of the first tree to be plucked, and a2 is the age of the second one. If there are several possible solutions, output any one.

Samples

InputOutput
2
1 1
2 2
1 1
2 2

Author
Discussion
Submit

Login to submit