<strong>题目描述</strong>

小青遇到了这样一个问题：The GNU Compiler Collection (GCC) is a compiler system produced by the GNU Project supporting various programming languages. But it does not contain the math operator. In mathematics the symbol represents the factorial operation. The expression n! means the product of the integers from 1 to n. For example, 4! is 4 x 3 x 2 x 1 = 24. 0! is defined as 1. We want you to help us with this formation: (0! + 1! + 2! + 3! + 4! + ... + n!)%m

<strong>输入格式</strong>

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.

<strong>输出格式</strong>

Output the answer of (0! + 1! + 2! + 3! + 4! + ... + n!)%m.

<strong>样例</strong>

<strong>样例 1</strong>

输入 # 1

3
4 5
0 1000
1000 1000

输出 # 1

2
1
973