SP14122 IRECSQRT - Inverse of Recurrence Problem With a Square Root

Given this recurrence formula (be careful, it's in inverse form):  Given **n** (0 n < 2 $ ^{64} $ ) and **m** (0 < **m** < 2 $ ^{64} $ ), your task is to compute a $ _{n} $ modulo **m**. It's guaranteed that a $ _{n} $ is always an integer.

First line containing an integer **T** (0 < **T** T cases follow. For each test case there're two integers **n** and **m**, writen in one line, separated by a space.

For each test case, output the required answer: a $ _{n} $ modulo **m**.