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 started to crying.Stop their crying by solve 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^15) 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.