In the real world, Bob is solving a programming problem but he is stuck on it. He is given Q (1 \(\leq\) Q \(\leq\) 10⁵) queries. Each query consists of two integers a and b (1 \(\leq\) a,b \(\leq\) 5*10⁵). For each query, he is required to find the minimum non-negative integer c such that a^c % b is 0 or a^c is divisible by b. If no such c exists, the answer for that query is -1. Can you help him ?

Input:
First line consists of a single integer Q, the number of queries.
Q lines follow. Each line represents a query and consists of two space separated integers a and b, as described above.

Output:
Print Q lines. In the i^th line, print the answer for i^th query.

Constraints:
1 \(\leq\) Q \(\leq\) 10⁵
1 \(\leq\) a,b \(\leq\) 5*10⁵