Problem Description

Cuber QQ has encountered a math problem during his research of "nothing related to math", he thought the problem too boring for him, and decided to leave it to you. You might be curious about more background about why this problem appeared in his research, but to save your time, let's say "the background isn't helpful for you to solve this problem".

Given $n$, $m$, count the number of sequence $x_1, x_2, \ldots, x_n$ such that $x_1^2 + x_2^2 + \cdots + x_{n-1}^2 \equiv x_n^2 \pmod m$ and $0 \le x_i < m$ for $1 \le i \le n$. $m$ is odd in this problem.

Input

The first line of the input is an integer $t$ ($1 \le t \le 2500$), where $t$ is the number of test cases.

Then follows $t$ test cases, each of which is a line with two space-separated integers $n$ and $m$ ($3 \le n \le 100, 3 \le m \le 999~999~999$ and $m$ is odd).

Output

For each test case, output the answer modulo $10^9 + 7$.

3
3 5
5 3
9 101

25
81
980480839