IRECSQRT - Inverse of Recurrence Problem With a Square Root

Given this recurrence formula (be careful, it's in inverse form):

Formula

Given n (0 ≤ n < 264) and m (0 < m < 264), your task is to compute an modulo m.

It's guaranteed that an is always an integer.

Input

First line containing an integer T (0 < T ≤ 5×104), than T cases follow.

For each test case there are two integers n and m, written in one line, separated by a space.

Output

For each test case, output the required answer: an modulo m.

Example

Input:
10
0 10
1 10
2 10
3 10
10 10
100 100
1000 1000
10000 10000
100000 100000
9876543210123456789 1234567890987654321

Output:
1
2
5
5
5
51
251
6251
6251
657422418465782775

Time limit ~7x My program speed: Click here to see my submission history and time record for this problem

See also: Another problem added by Tjandra Satria Gunawan


Added by:Tjandra Satria Gunawan
Date:2013-03-14
Time limit:13s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:ONMIPA sel 2013

hide comments
2013-03-15 06:43:14 (Tjandra Satria Gunawan)(曾毅昆)
This is the first time I made problem with require BigNum operation :-) I hope I can learn faster method for BigNum operation (especially using C language). Took ~12 hours to set this problem. I hope everyone enjoyed this problem, Have Fun! :-D

Last edit: 2013-03-15 06:42:57
2013-03-15 06:05:13 [Rampage] Blue.Mary
Pike is so slow comparing to Python 2.7.
Ans: Yes PIKE is slower than Python for this problem, I set the time limit so that it has a chance to solve this problem using most slow language. And congratulations, You're the first solver :-D

Last edit: 2013-03-15 06:41:18
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.