## ALMISPY - Almost-isosceles Pythagorean triple (easy)

no tags

(3, 4, 5) is the smallest almost-isosceles Pythagorean triple, as 4 - 3 = 1.
Let S = { (a, a+1, c) | a2 + (a+1)2 = c2 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.)