Euler's totient function counts the number of positive integers less than that are coprime to. That is,ϕ(n) is the number of such that and , and additionally by definition.
Here are totally queries, each one contains two positive integers , and we need you to calculate. Because the answer may be large,and only have a one-bit-memory, you must find it modulo.
Input
The first line contains one positive integer, represents the number of queries.
The nextlines contain two positive integers
Output
The output containslines, each line contains one integer, represents the answer.