## DELTACA2 - Delta catheti II (Hard)

**(3, 4, 5)** is a famous Pythagorean triple,
it gives a quick answer to the question:

For a given integer ** d**, is there a Pythagorean triple

**(**such that

*a, b, c*)**?**

*b - a = d*
A solution is **(3 d, 4d, 5d)**,
and in fact one can easily prove that the set of solutions is infinite, and
that there is an obvious total order on those solutions.

Given

**, you'll have to find the**

*n***th term of the sequence of solutions.**

*n*Geometrically, it is the study of right angle triangles for which the difference of the
catheti is equal to ** d**.

### Input

The first line of input contains an integer
** T**, the number of test cases.

**2 T** lines follow. Each case is on two lines.

The first line of the case contains three integers

**.**

*n, d, m*The second line contains an integer

**and**

*L***2**other integers (p, e) ; this gives the prime factorization of

*L***in standard format (d = product p^e).**

*d*### Output

For each test case, compute the ** n**th term amongst
the solutions

**(**for the problem :

*a, b, c*)**with**

*a*^{2}+ b^{2}= c^{2}**and**

*b - a = d***.**

*0 < a < b < c*As the answer could not fit in a 64-bit container, simply output your answer modulo ** m**.

### Example

Input:3 1 1 235813 0 3 21 1000 2 3 1 7 1 9 119 11 2 7 1 17 1

Output:3 4 5 63 84 105 5 3 1

### Explanations

For the first case, the first solution is **(3, 4, 5)**, as 4 - 3 = 1.

For the second case, the first solutions are:

**(15, 36, 39), (24, 45, 51), (63, 84, 105), (144, 165, 219), (195, 216, 291), (420, 441, 609), ...**

The third one is **(63, 84, 105)**.

For the third case, the first solutions are:

**(24, 143, 145), (49, 168, 175), (57, 176, 185), (85, 204, 221), (136, 255, 289),
(180, 299, 349), (196, 315, 371), (261, 380, 461), (357, 476, 595), (481, 600, 769),
(616, 735, 959), ... **

The 9th solution is **(357, 476, 595)**, reduced modulo 11, we get
**(5, 3, 1)**.

### Constraints

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

** d** is the product of two integers lower than 10^7.

**: Uniform randomly chosen in their range.**

*n, d*_{1}, d_{2}, mThose constraints are set to allow C-like users to work only with 64bit containers.

For your information, my 3kB-python3 code get AC in 1.22s. (Edit 2017-02-11, after compiler change)

It should be much faster with a compiled language.

**Warning** : It's my hardest problem.
Have fun ;-)

Added by: | Francky |

Date: | 2013-04-21 |

Time limit: | 10s |

Source limit: | 50000B |

Memory limit: | 1536MB |

Cluster: | Cube (Intel G860) |

Languages: | All except: ASM64 |

Resource: | Own problem |