← 返回题目列表

Codeforces · 1370/A

A. 最大 GCD

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

让我们考虑从 $$$1$$$ 到 $$$n$$$(含)范围内的所有整数。

在此范围内的所有不同整数对中,找到该对中整数的最大可能最大公约数。形式上,求 $$$\mathrm{gcd}(a, b)$$$ 的最大值,其中 $$$1 \leq a < b \leq n$$$。

两个正整数 $$$a$$$ 和 $$$b$$$ 的最大公约数 $$$\mathrm{gcd}(a, b)$$$ 是 $$$a$$$ 和 $$$b$$$ 的约数的最大整数。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 100$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的唯一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 10^6$$$)。

输出

对于每个测试用例,输出所有 $$$1 \leq a < b \leq n$$$ 中 $$$\mathrm{gcd}(a, b)$$$ 的最大值。

示例

输入 #1

2
3
5

输出 #1

1
2

注意

在第一个测试用例中, $$$\mathrm{gcd}(1, 2) = \mathrm{gcd}(2, 3) = \mathrm{gcd}(1, 3) = 1$$$。

在第二个测试用例中,$$$2$$$ 是最大可能值,对应于 $$$\mathrm{gcd}(2, 4)$$$。