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⁵