AT_abc400_e [ABC400E] Ringo's Favorite Numbers 3

正整数 $ 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 は常に存在します。

入力は以下の形式で標準入力から与えられる。 > $ Q $ $ \text{query}_1 $ $ \text{query}_2 $ $ \vdots $ $ \text{query}_Q $ ここで、 $ \text{query}_i $ は $ i $ 番目のクエリであり、以下の形式で与えられる。 > $ A $

$ Q $ 行出力せよ。 $ i $ 行目には $ i $ 番目のクエリに対する答えを出力せよ。

### Sample Explanation 1 $ 1 $ 番目のクエリについて説明します。 $ 400 $ の素因数は $ 2, 5 $ のちょうど $ 2 $ 種類であり、 $ 400 $ が $ 2 $ で割り切れる回数は $ 4 $ 回、 $ 5 $ で割り切れる回数は $ 2 $ 回であるため $ 400 $ は 400 number です。 $ 401, 402, 403, 404 $ は 400 number ではないため答えは $ 400 $ となります。 ### Constraints - $ 1 \leq Q \leq 2 \times 10^5 $ - 各クエリについて、 $ 36 \leq A \leq 10^{12} $ - 入力される値はすべて整数