CF2218D The 67th OEIS Problem

Macaque, being a terrible problemsetter, decided to search for funny sequences on the OEIS $ ^{\text{∗}} $ one day, so he could gain inspiration for his doomed problemsetting job for the Pan-Mammalian Olympiad in Informatics (PMOI). To his delight, he found one, and thought it would be funny to make you, his loyal tester, solve it: Construct a sequence $ a $ containing $ n $ integers such that $ \operatorname{gcd}(a_i, a_{i+1}) $ $ ^{\text{†}} $ is distinct over all $ 1 \leq i \leq n - 1 $ . It is guaranteed that at least one sequence $ a $ exists. $ ^{\text{∗}} $ Online Encyclopedia of Integer Sequences, the favourite website of math nerds, overly astute testers, and insufficiently rigorous coordinators. $ ^{\text{†}} $ $ \operatorname{gcd}(x,y) $ refers to the [greatest common divisor](https://en.wikipedia.org/wiki/Greatest_common_divisor) of integers $ x $ and $ y $ .

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 100 $ ). The description of the test cases follows. The following $ t $ lines contain one integer $ n $ ( $ 2 \leq n \leq 10^4 $ ) — the desired length of the sequence. It is guaranteed the sum of $ n $ over all test cases does not exceed $ 10^4 $ .

For each query, output your answer — a sequence $ a $ of $ n $ space-separated integers ( $ 1 \le a_i \le 10^{18} $ ).

In the first test case, the sequence $ [1, 6, 2] $ is a possible answer. This is because $ \gcd(1, 6) $ is not equal to $ \gcd(6, 2) $ . In the second test case, the sequence $ [134, 67, 69, 207, 414] $ is a possible answer. This is because the values of $ \gcd(a_i, a_{i+1}) $ for all $ i $ between $ 1 $ and $ n-1 $ are distinct. For reference, they are $ 67 $ , $ 1 $ , $ 69 $ and $ 207 $ .