Dividing Stones

Time limit7sMemory limit1024 MB

Summary

Given N and P, count the distinct values that the product of pile sizes modulo P can take over all ways to split N stones into piles.

Level: Medium6 of 10
Topics: Dynamic programming, Hash map, Number theory
Solved: No attempts yet

Problem

There are N stones, which can be divided into some piles arbitrarily. The value of each division is equal to the product of the number of stones in all the piles, modulo P. For a given N and P, how many distinct values are possible?

Input

The first line contains the number of test cases T. Each of the next T lines contains two integers N and P.

Output

Output T lines. Each line contains the answer for the corresponding test case.

Constraints

T ≤ 20
2 ≤ N ≤ 70
2 ≤ P ≤ $10^9$

Hint

In the first test case, the possible divisions are (1,1,1), (1,2), (2,1), and (3), with values 1, 2, 2, and 3. So there are 3 distinct values.

In the second test case, the numbers 1 to 6 are the answer, and they can be obtained as follows:

1=1*1*1*1*1
2=2*1*1*1
3=3*1*1
4=4*1
5=5
6=2*3

Examples1

Example 1
Input
```
2
3 1000
5 1000
```
Expected output
```
3
6
```