Macaque, будучи ужасным составителем задач, однажды решил поискать забавные последовательности на OEIS$$$^{\text{∗}}$$$, чтобы вдохновиться для своей обречённой работы по составлению задач для Панмлекопитающей олимпиады по информатике (PMOI). К своей радости, он нашёл одну и решил, что будет забавно заставить вас, своего верного тестировщика, решить её:
Постройте последовательность $$$a$$$, содержащую $$$n$$$ целых чисел, такую, что значения $$$\operatorname{gcd}(a_i, a_{i+1})$$$ $$$^{\text{†}}$$$ различны для всех $$$1 \leq i \leq n - 1$$$. Гарантируется, что существует хотя бы одна такая последовательность $$$a$$$.
$$$^{\text{∗}}$$$Online Encyclopedia of Integer Sequences — любимый сайт математических зануд, чрезмерно проницательных тестировщиков и недостаточно строгих координаторов.
$$$^{\text{†}}$$$$$$\operatorname{gcd}(x,y)$$$ обозначает наибольший общий делитель целых чисел $$$x$$$ и $$$y$$$.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Следующие $$$t$$$ строк содержат по одному целому числу $$$n$$$ ($$$2 \leq n \leq 10^4$$$) — требуемую длину последовательности.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$10^4$$$.
Для каждого запроса выведите ответ — последовательность $$$a$$$ из $$$n$$$ целых чисел, разделённых пробелами ($$$1 \le a_i \le 10^{18}$$$)
2 3 5
1 6 2 134 67 69 207 414
В первом наборе входных данных последовательность $$$[1, 6, 2]$$$ является возможным ответом. Это так, потому что $$$\gcd(1, 6)$$$ не равно $$$\gcd(6, 2)$$$.
Во втором наборе входных данных последовательность $$$[134, 67, 69, 207, 414]$$$ является возможным ответом. Это так, потому что значения $$$\gcd(a_i, a_{i+1})$$$ для всех $$$i$$$ от $$$1$$$ до $$$n-1$$$ различны. Для справки, это $$$67$$$, $$$1$$$, $$$69$$$ и $$$207$$$.
| Codeforces Round 1090 (Div. 4) |
|---|
| Закончено |
