题目描述

对于正整数 $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

输入 #1

5
404
36
60
1000000000000
123456789

输出 #1

400
36
36
1000000000000
123454321

说明/提示

约束条件

• $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 完成