AT_abc400_e [ABC400E] Ringo's Favorite Numbers 3

[problemUrl]: https://atcoder.jp/contests/abc400/tasks/abc400_e 对于正整数 $N$，当且仅当满足以下两个条件时，$N$ 被称为 **400 number**： - $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$ 个查询的答案。

### 约束条件 - $1 \leq Q \leq 2 \times 10^5$ - 对于每个查询，$36 \leq A \leq 10^{12}$ - 输入中的所有值均为整数 ### 样例解释 1 以第一个查询为例： $400$ 的素因数恰好为 $2$ 和 $5$ 两种。$400$ 被 $2$ 整除的次数为 $4$ 次（偶数次），被 $5$ 整除的次数为 $2$ 次（偶数次），因此 $400$ 是 400 number。而 $401$、$402$、$403$、$404$ 均不是 400 number，故答案为 $400$。 翻译由 DeepSeek R1 完成