(3, 4, 5) is the smallest almost-isosceles Pythagorean triple, as 4 - 3 = 1.
Let S = { (a, a+1, c) | a² + (a+1)² = c² with a and c positive integers}.
One can prove that the set S of almost-isosceles Pythagorean triples is infinite.
There is an obvious total order on this set.

Input

The first line of input contains an integer T, the number of test cases.
On each of the next T lines, your are given two integers n and m.

Output

For each test case, you have to find the nth triple (a, a+1, c) in the ordered set S, and print a and c. As the answer could not fit in a 64-bit container, simply output your answer modulo m.

Example

Input:
3
1 10
2 123
4 289

Output:
3 5
20 29
118 118

Constraints

0 < T < 10^4
0 < n < 10^18
1 < m < 10^9

For your information, my 500B-python3 code get AC in 1.61s with 12MB of memory print.
In Python2.7 : (2.49s, 4.0MB), in Python2+psyco (2.04s, 36MB).
My 1kB C code ran in (0.04s, 1.6MB), and time limit is ×125 this one.
Have fun ;-)
(edit) With wisfaq observation, all my best timings are divided by exactly two!!!
(Edit 2017-02-11, new TL with new compiler. TL 1.11s, in the third (0.37s) my Python3 code ends.)