Dividing Stones
시간 제한7초메모리 제한1024 MB
N개의 돌을 임의로 여러 더미로 나눈 뒤 더미 크기의 곱을 P로 나눈 나머지로 만들 수 있는 서로 다른 값의 개수를 구한다.
문제
There are N stones, which can be divided into some piles arbitrarily. Let the value of each division be equal to the product of the number of stones in all the piles modulo P. How many possible distinct values are possible for a given N and P?
입력
The first line contains the number of test cases T. T lines follow, one corresponding to each test case, containing 2 integers: N and P.
출력
Output T lines, each line containing the required answer for the corresponding test case.
제한
- T ≤ 20
- 2 ≤ N ≤ 70
- 2 ≤ P ≤ 109
힌트
In the first test case, the possible ways of division are (1,1,1), (1,2), (2,1) and (3) which have values 1, 2, 2, 3 and hence, there are 3 distinct values.
In the second test case, the numbers 1 to 6 constitute the answer and they can be obtained in the following ways:
- 1=1*1*1*1*1
- 2=2*1*1*1
- 3=3*1*1
- 4=4*1
- 5=5
- 6=2*3