/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 425 点
問題文
正整数 N に対し、N が 400 number であることは以下の 2 つの条件をともに満たすことであると定義します。
- N の素因数はちょうど 2 種類である。
- N の各素因数 p について、N が p で割り切れる回数は偶数回である。より厳密には、N の各素因数 p について p^k が N の約数であるような最大の非負整数 k は偶数である。
Q 個のクエリが与えられるので、それぞれについて答えてください。各クエリでは、整数 A が与えられるので、A 以下の最大の 400 number の値を求めてください。ただし、本問題の制約下では A 以下の 400 number は常に存在します。
制約
- 1 \leq Q \leq 2 \times 10^5
- 各クエリについて、36 \leq A \leq 10^{12}
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
Q
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q
ここで、\text{query}_i は i 番目のクエリであり、以下の形式で与えられる。
A
出力
Q 行出力せよ。i 行目には i 番目のクエリに対する答えを出力せよ。
入力例 1
5 404 36 60 1000000000000 123456789
出力例 1
400 36 36 1000000000000 123454321
1 番目のクエリについて説明します。
400 の素因数は 2, 5 のちょうど 2 種類であり、400 が 2 で割り切れる回数は 4 回、5 で割り切れる回数は 2 回であるため 400 は 400 number です。401, 402, 403, 404 は 400 number ではないため答えは 400 となります。
Score : 425 points
Problem Statement
A positive integer N is a 400 number if and only if it satisfies both of the following two conditions:
- N has exactly 2 distinct prime factors.
- For each prime factor p of N, p divides N an even number of times. More formally, the maximum non-negative integer k such that p^k divides N is even.
Process Q queries. Each query gives you an integer A, so find the largest 400 number not exceeding A. Under the constraints of this problem, a 400 number not exceeding A always exists.
Constraints
- 1 \leq Q \leq 2 \times 10^5
- For each query, 36 \leq A \leq 10^{12}.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
Q
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q
Here, \text{query}_i is the i-th query, given in the following format:
A
Output
Print Q lines. The i-th line should contain the answer to the i-th query.
Sample Input 1
5 404 36 60 1000000000000 123456789
Sample Output 1
400 36 36 1000000000000 123454321
Let us explain the first query.
There are exactly 2 prime factors of 400: 2 and 5. Also, 2 divides 400 four times and 5 divides it twice, so 400 is a 400 number. None of 401, 402, 403, and 404 is a 400 number, so the answer is 400.