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

Given n (0 ≤ n < 2⁶⁴) and m (0 < m < 2⁶⁴), your task is to compute a_n modulo m.

It's guaranteed that a_n is always an integer.

Input

First line containing an integer T (0 < T ≤ 5×10⁴), 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: a_n 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