SP8063 AMR10I - Dividing Stones

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? **INPUT** 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** Output T lines, each line containing the required answer for the corresponding test case. **CONSTRAINTS** T

N/A

N/A