AT_abc400_e [ABC400E] Ringo's Favorite Numbers 3

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.

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 $

Print $ Q $ lines. The $ i $ -th line should contain the answer to the $ i $ -th query.

### Sample Explanation 1 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 $ . ### Constraints - $ 1 \leq Q \leq 2 \times 10^5 $ - For each query, $ 36 \leq A \leq 10^{12} $ . - All input values are integers.