Sometimes inventing a story for the problem is a very hard task. Fortunately for us, Limak has just been kidnapped by an insane mathematician. We need some name for the mathematician and let it be Mathew.

Limak is a little polar bear. He has been kidnapped and now must deal with puzzles invented by Mathew. There were many of them but only one remains.

Mathew is crazy about permutations of numbers from 1 to n. He says that the score of permutation \(p_1, p_2, \ldots, p_n\) is equal to: \(\prod_{1 \le i < j \le n} gcd(|i - j|, |p_i - p_j|)\)

For example, a permutation \((3, 2, 1, 4)\) has score: \(gcd(1, 3-2) \cdot gcd(2, 3-1) \cdot gcd(3, 4-3) \cdot gcd(1, 2-1) \cdot gcd(2, 4-2) \cdot gcd(1, 4-1) = 1 \cdot 2 \cdot 1 \cdot 1 \cdot 2 \cdot 1 = 4\)

Let \(X_n\) denote the sum of scores of all permutations of numbers from 1 to n.

Limak must be able to answer questions about value \(X_n\) modulo m for given numbers n and m where m is prime. If he succeeds then he can go home and take the prize — a chest full of candies and fish. If he fails then he goes home anyway but without anything delicious to eat.

Would you be able to get candies and fish? Find \(X_n\) modulo m for each question.

Input format

The first line contains one integer T — the number of questions.

Each of the next T lines contains two integers n and m describing one question. Number m is guaranteed to be prime.

Output format

For each question, print the answer in a separate line.

Constraints

• \(1 \le T \le 100\)
• \(2 \le n \le 12\)
• \(2 \le m \le 10^9\) and m is prime

There are 5 test files, satisfying \(n \le 6, n \le 8, n \le 10, n \le 11, n \le 12\) respectively. Each test file is worth \(20\) points.