Oleg's favorite subjects are History and Math, and his favorite branch of mathematics is division.

To improve his division skills, Oleg came up with t pairs of integers p_i and q_i and for each pair decided to find the greatest integer x_i, such that: 

  * p_i is divisible by x_i; 
  * x_i is not divisible by q_i. 

Oleg is really good at division and managed to find all the answers quickly, how about you?

Input

The first line contains an integer t (1 ≤ t ≤ 50) — the number of pairs.

Each of the following t lines contains two integers p_i and q_i (1 ≤ p_i ≤ 10^{18}; 2 ≤ q_i ≤ 10^{9}) — the i-th pair of integers.

Output

Print t integers: the i-th integer is the largest x_i such that p_i is divisible by x_i, but x_i is not divisible by q_i.

One can show that there is always at least one value of x_i satisfying the divisibility conditions for the given constraints.

Example

Input


3
10 4
12 6
179 822


Output


10
4
179

Note

For the first pair, where p_1 = 10 and q_1 = 4, the answer is x_1 = 10, since it is the greatest divisor of 10 and 10 is not divisible by 4.

For the second pair, where p_2 = 12 and q_2 = 6, note that 

  * 12 is not a valid x_2, since 12 is divisible by q_2 = 6; 
  * 6 is not valid x_2 as well: 6 is also divisible by q_2 = 6. 

The next available divisor of p_2 = 12 is 4, which is the answer, since 4 is not divisible by 6.
//JDope
import java.util.*;
import java.io.*;
import java.math.*;
public class C{
public static void main(String[] omkar) throws Exception
{
   BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
   StringTokenizer st = new StringTokenizer(in.readLine());
   StringBuilder sb = new StringBuilder();
   int cases = Integer.parseInt(st.nextToken());
   long a, b, c, d, maxx;
   for(int j = 0; j < cases; j++)
   {
      st = new StringTokenizer(in.readLine());
      a = Long.parseLong(st.nextToken());
      b = Long.parseLong(st.nextToken());
      maxx = (long)(1);
      if(a % b != 0)
      {
         sb.append(a+"\n");
      }
      else
      {
         for(int i = 1; i <= (int)(Math.sqrt(b)); i++)
         {
            if(b % i == 0)
            {
               c = a;
               while(c % b == 0 && c % i == 0 && c/i < c && i != 1)
               {
                  c = c/(long)(i);
               }
               if(c % b != 0)
               {
                  maxx = Math.max(maxx, c);
               }
               c = a;
               d = b/(long)(i);
               while(c % b == 0 && c % d == 0 && c/d < c)
               {
                  c = c/d;
               }
               if(c % b != 0)
               {
                  maxx = Math.max(maxx, c);
               }
            }
         }
         sb.append(maxx+"\n");
      }
   }  
   System.out.println(sb);
        }
 public static int[] readArr(int N, BufferedReader in, StringTokenizer st) throws Exception
      {
         int[] arr = new int[N];
         st = new StringTokenizer(in.readLine());
         for(int i=0; i < N; i++)
            arr[i] = Integer.parseInt(st.nextToken());
         return arr;
      }


}