← 返回题目列表

AtCoder · abc400_e

H. 林戈最喜欢的数字 3

中文机器翻译题面 查看原题

分数: 425 点

问题陈述

正整数 N 是 400号 当且仅当满足以下两个条件:

  • N 正是 2 不同的质因数。
  • 对于每个质因数 p of N, p 划分 N 偶数次。更正式地说,最大非负整数 k 这样 p^k 划分 N 是偶数。

流程 Q 查询。每个查询都会给你一个整数 A,所以找到最大不超过400的数 A。在这个问题的约束下,400个数不超过 A 始终存在。

约束

  • 1 \leq Q \leq 2 \times 10^5
  • 对于每个查询, 36 \leq A \leq 10^{12}.
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

Q
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q

在这里, \text{query}_i 是 i-第一个查询,按以下格式给出:

A

输出

打印 Q 行。的 i- 第行应包含以下问题的答案 i第一个查询。


示例输入 1

5
404
36
60
1000000000000
123456789

示例输出 1

400
36
36
1000000000000
123454321

让我们解释一下第一个查询。

正好有 2 的质因数 400: 2 和 5。另外, 2 划分 400 四次并且 5 将其除两次,所以 400 是一个 400 号码。没有一个 401, 402, 403,和 404 是一个 400 数字,所以答案是 400.