NUMTHEO01 - Mad Mod


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 1015) 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.



Added by:Ruhul
Date:2019-09-14
Time limit:4s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:C CPP14 JAVA PYTHON3