题目描述

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

更形式化地说：对于每个质因数 $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

以第一个查询为例：

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

$10\%$ 的数据满足：

$35\%$ 的数据满足：

$100\%$ 的数据满足：