题目描述

如果一个正整数 $N$ 同时满足下面两个条件，那么称 $N$ 是一个 400 数：

• $N$ 恰好有 $2$ 个不同的质因数。
• 对于 $N$ 的每一个质因数 $p$，$p$ 在 $N$ 中出现的次数都是偶数。

更形式化地说：对于每个质因数 $p$，满足 $p^k\mid N$ 的最大非负整数 $k$ 必须是偶数。

现在需要处理 $Q$ 个询问。

每个询问给定一个整数 $A$，请你求出不超过 $A$ 的最大 400 数。

在本题的数据范围内，保证对于每个询问，都存在一个不超过 $A$ 的 400 数。

输入格式

第一行输入一个整数 $Q$。

接下来 $Q$ 行，每行一个整数 $A$。

输出格式

输出 $Q$ 行。第 $i$ 行应输出第 $i$ 个查询的答案。

5
404
36
60
1000000000000
123456789

400
36
36
1000000000000
123454321

样例 1 解释

以第一个查询为例：

• $400$ 的素因数恰好为 $2$ 和 $5$ 两种。$400$ 被 $2$ 整除的次数为 $4$ 次（偶数次），被 $5$ 整除的次数为 $2$ 次（偶数次），因此 $400$ 是 400 数。而 $401$、$402$、$403$、$404$ 均不是 400 数，故答案为 $400$。

数据范围

$10\%$ 的数据满足：

• $1 \leq Q \leq 10$
• 对于每个查询，$36 \leq A \leq 10^{4}$

$35\%$ 的数据满足：

• $1 \leq Q \leq 100$
• 对于每个查询，$36 \leq A \leq 10^{12}$

$100\%$ 的数据满足：

• $1 \leq Q \leq 2 \times 10^5$
• 对于每个查询，$36 \leq A \leq 10^{12}$