CF2158F1 Distinct GCDs (Easy Version)

这是该题的简单版本。不同版本的区别在于本版本中 $n \leq 700$。你只有在解决了所有版本的问题后才能进行 hack。 传说中，高斯小时候在课堂上，老师让同学们计算 $1$ 到 $100$ 的整数和，想以此让他们安静一阵。但小高斯很快就写出了 $\text{sum} = \frac{n(n+1)}{2}$ 的公式，瞬间得出了答案。几个世纪后，高斯在你的梦中出现，并带来了一项艰巨的任务…… 给定一个正整数 $n$，请你构造一个长度为 $n$ 的整数序列 $[a_1, a_2, \ldots, a_n]$，使得对于所有 $1 \leq i \leq n$ 有 $1 \leq a_i \leq 10^{18}$，并且相邻任意两个元素的最大公约数均不相同。形式化地说， 对于 $1 \leq i < j < n$，都有 $\gcd(a_i, a_{i+1}) \neq \gcd(a_j, a_{j+1})$。 此外，要求 $a$ 中不同元素的数量尽可能少。

每个测试点包含多组测试数据。第一行包含一个整数 $t$（$1 \leq t \leq 200$），表示测试数据的组数。 接下来每组测试数据包含一行，包含一个整数 $n$（$2 \leq n \leq 700$），表示需构造的序列长度。

对于每组测试数据，输出 $n$ 个用空格分隔的正整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq 10^{18}$），使得它们满足题目的要求。若有多组满足条件的解，输出任意一组均可。 可以证明，在题目给定的约束范围内，总是存在解。

对于第二组样例，相邻元素的最大公约数为 $[\gcd(1, 4), \gcd(4, 4), \gcd(4, 6), \gcd(6, 6)] = [1, 4, 2, 6]$，均不相同。 对于第三组样例，相邻元素的最大公约数为 $[\gcd(4, 4), \gcd(4, 6), \gcd(6, 6), \gcd(6, 9), \gcd(9, 9), \gcd(9, 4)] = [4, 2, 6, 3, 9, 1]$，均不相同。 对于每组测试数据，都可以证明，无法使用更少的不同元素得到所有相邻最大公约数均不同的序列。 由 ChatGPT 5 翻译