돌 나누기

N개의 돌이 있고, 이 돌들을 임의의 개수의 더미로 나눌 수 있다. 각 나눔의 값은 모든 더미에 있는 돌 개수의 곱을 P로 나눈 나머지이다. 주어진 N과 P에 대해 가능한 서로 다른 값은 몇 개인가?

첫 줄에 테스트 케이스의 개수 T가 주어진다. 이어서 T개의 줄에 각각 정수 N과 P가 주어진다.

T개의 줄을 출력한다. 각 줄에는 해당 테스트 케이스의 답을 출력한다.

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

첫 번째 테스트 케이스에서 가능한 나눔은 (1,1,1), (1,2), (2,1), (3)이며, 값은 각각 1, 2, 2, 3이다. 따라서 서로 다른 값은 3개이다.

두 번째 테스트 케이스에서는 1부터 6까지의 수가 모두 답이 되며, 다음과 같이 만들 수 있다.

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