Moduling(%) is a famous operation in programming world. Sometimes kids love to mod(%) a number by another number. They also love to calculate factorial as factorial is a sequential multiplying process. But they noticed to calculate (70!) the scientific calculator returned "Math Error", and they started crying. Stop their crying by solving this problem.

Input

The first line contains t (1 ≤ t ≤ 15) the number of queries.The first line of each queriy contains two integers n and x (n is less than 8388700 and x is less than 10¹⁵) where n is for getting factorial value and x is moduling value.

Output

Your task is to calculate (n!) % x.

Example

Input:
3
5 7
10 231
1 1

Output:
1
21
0

Note: Here in first input 5! = 1×2×3×4×5 or 120. Then 120 % 7 = 1.