Илья очень любит графы, особенно деревья. Во время последнего похода в лес Илья нашел очень интересное дерево с корнем в вершине 1, в каждой вершине i которого записано одно целое число ai.
Красотой вершины x Илья называет наибольший общий делитель всех чисел в вершинах на пути от корня до x включительно. При этом Илья может изменить число в одной произвольной вершине на 0, либо оставить все вершины неизменными. Теперь Илью интересует, какая максимальная красота может быть у каждой вершины.
Для каждой вершины ответ нужно считать независимо.
Красота корня равна числу, записанному на нем.
Выходные данные
В единственной строке через пробел выведите n чисел, где i-е по порядку числу — максимальная красота вершины i.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
6 2
1 2
|
6 6
|
|
2
|
3
6 2 3
1 2
1 3
|
6 6 6
|
|
3
|
1
10
|
10
|