Background

Luogu’s testdata is only for non-official communication and is not official testdata. Official judging link: https://www.cspro.org/.

Problem Description

A prime number (also called a “prime”) is a natural number greater than $1$ that has no divisors other than $1$ and itself.

After learning the concept of prime numbers, student P learned that any positive integer $n$ can be uniquely represented as a product of several prime factors. If the positive integer $n$ has $m$ distinct prime factors $p_1, p_2, \cdots, p_m$, then it can be written as: $n = p_1^{t_1} \times p_2^{t_2} \times \cdots \times p_m^{t_m}$.

Student P believes that the exponent $t_i$ corresponding to each prime factor reflects how important that prime factor is to $n$. Now set a threshold $k$. If the exponent $t_i$ corresponding to some prime factor $p_i$ is less than $k$, then this prime factor is considered unimportant, and the term $p_i^{t_i}$ can be removed by dividing it out from $n$. Otherwise, keep the term $p_i^{t_i}$. The product of the remaining terms is the simplified value of $n$. If no terms remain, then the simplified value is considered to be $1$.

Write a program to process $q$ queries:

• Each query contains two positive integers $n$ and $k$, and you need to compute the simplified value of $n$ according to the method above.

Input Format

Read data from standard input.

The input consists of $q + 1$ lines.

The first line contains a positive integer $q$, indicating the number of queries.

Each of the next $q$ lines contains two positive integers $n$ and $k$, indicating a query.

Output Format

Write to standard output.

The output consists of $q$ lines.

Each line outputs a positive integer, indicating the result for the corresponding query.

3
2155895064 3
2 2
10000000000 10

2238728
1
10000000000

Hint

Sample Explanation

Query 1:

• $n = 2^3 \times 3^2 \times 23^4 \times 107$
• The prime factor $3$ has exponent $2$, and $107$ has exponent $1$. After removing these two terms from $n$, the product of the remaining terms is $2^3 \times 23^4 = 2238728$.

Query 2:

• All terms are removed, output $1$.

Query 3:

• All terms are kept, output $n$ as is.

Subtasks

$40\%$ of the testdata satisfies: $n \le 1000$.

$80\%$ of the testdata satisfies: $n \le 10^5$.

All testdata satisfies: $1 < n \le 10^{10}$ and $1 < k, q \le 10$.

Translated by ChatGPT 5