The first line consists of an integer T, indicating the number of test cases.
Each test on a single consists of two integer n and m.
Output the answer of (0! + 1! + 2! + 3! + 4! + ... + n!)%m.
Constrains
0 < T <= 20
0 <= n < 10^100 (without leading zero)
0 < m < 1000000
1
10 861017
593846