An array of integers is called -coprime if the following conditions are both satisfied:
- All the integers in the array are positive divisors of .
- Each pair of adjacent elements in the array is coprime (i.e., element is always coprime with element ).
Two arrays, and , of size are different if and only if there exists an index such that .
You are given queries where each query consists of integers and . For each query, find the number of -coprime arrays of size , modulo , and print it on a new line.
Input Format
The first line contains an integer, , denoting the number of queries.
Each of the subsequent lines contains two space-separated integers describing the respective values of (the size of the array) and .
Constraints
Output Format
For each query, print the number of -coprime arrays of size modulo on a new line.
Sample Input 0
1
2 6
Sample Output 0
9
Explanation 0
Given and , we want to find the possible -coprime arrays of length . The elements of each array must be taken from the set of divisors of , which is for the given value of . We then assemble all possible -coprime arrays of size :
As there are nine such arrays, we print the value of on a new line.