← 返回题目列表

Codeforces · 2158/F1

F1. 独特的 GCD(简单版)

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

这是问题的简单版本。版本之间的差异在于,在此版本中,$$$n \leq 700$$$。只有解决了该问题的所有版本,您才能破解。

传说,当高斯还是个小学生时,他的老师要求全班同学对从 $$$1$$$ 到 $$$100$$$ 的整数求和,这可能是为了让他们暂时忙碌起来。然而,年轻的高斯很快就想出了公式 $$$\text{sum} = \frac{n(n+1)}{2}$$$ 并立即找到了答案。几个世纪后,高斯在一场噩梦中出现在你面前,肩负着一项艰巨的任务……

给定一个正整数$$$n$$$,找到一个整数序列$$$[a_1, a_2, \ldots, a_n]$$$,使得$$$1 \leq a_i \leq 10^{18}$$$对于所有$$$1 \leq i \leq n$$$,以及$$$a$$$的成对相邻元素的GCD都是不同的。正式地,

$$$\gcd(a_i, a_{i+1}) \neq \gcd(a_j, a_{j+1})$$$ 对于每个 $$$1 \leq i \lt j \lt n$$$

此外,$$$a$$$ 应该具有 最低可能 不同元素的数量。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 200$$$)。测试用例的描述如下。

每个测试用例的第一行也是唯一一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 700$$$) — 要查找的序列的大小。

输出

对于每个测试用例,在满足语句中条件的新行上输出 $$$n$$$ 空格分隔的正整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^{18}$$$)。如果有多个解决方案,请打印其中任何一个。

可以证明,在问题约束下,解总是存在。

示例

输入
复制

3
2
5
7

输出
复制

2 2
1 4 4 6 6
4 4 6 6 9 9 4

注意

对于第二个测试用例,相邻元素的 GCD 为 $$$[\gcd(1, 4), \gcd(4, 4), \gcd(4, 6), \gcd(6, 6)] = [1, 4, 2, 6]$$$,所有这些都是不同的。

对于第三个测试用例,相邻元素的 GCD 为 $$$[\gcd(4, 4), \gcd(4, 6), \gcd(6, 6), \gcd(6, 9), \gcd(9, 9), \gcd(9, 4)] = [4, 2, 6, 3, 9, 1]$$$,所有这些都是独特的。

对于每个测试用例,可以证明不存在具有更少不同元素的序列,使得所有相邻 GCD 都是不同的。