当前没有测试数据。

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're two integers n and m, writen 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:

</p>

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