P16065 [CSPro 32] Factor Simplification

Luogu’s testdata is only for non-official communication and is not official testdata. Official judging link: .

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.

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.

Write to standard output. The output consists of $q$ lines. Each line outputs a positive integer, indicating the result for the corresponding query.

### 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