Черепаха только что научилась умножать два целых числа на уроке математики и была очень взволнована.
Затем Свинка дала ей целое число \(n\) и попросила построить последовательность \(a_1, a_2, \ldots, a_n\), состоящую из целых чисел, которые удовлетворяли бы следующим условиям:
- Для всех \(1 \le i \le n\), \(1 \le a_i \le 3 \cdot 10^5\).
- Для всех \(1 \le i < j \le n - 1\), \(a_i \cdot a_{i + 1} \ne a_j \cdot a_{j + 1}\).
Из всех таких последовательностей Пятачок попросил Черепаху найти ту, в которой будет минимальное количество различных элементов.
Черепаха определенно не смогла бы решить задачу, поэтому пожалуйста, помогите ей!
Выходные данные
Для каждого тестового случая выведите \(n\) целых чисел \(a_1, a_2, \ldots, a_n\) — элементы последовательности \(a\).
Если существует несколько ответов, выведите любой из них.
Примечание
В третьем тестовом случае \(a = [3, 4, 2, 6]\) нарушает второе условие, так как \(a_1 \cdot a_2 = a_3 \cdot a_4\). \(a = [2, 3, 4, 4]\) удовлетворяет условиям, но количество различных элементов в нем не минимально.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
2
3
4
|
114514 114514
1 2 2
3 3 4 4
|