В космической лаборатории каждая панель имеет номер от 0 до n.

Номер панели записывается в двоичной системе счисления. Если в каком-то разряде стоит 1, то соответствующий световой модуль включён. Если в разряде стоит 0, то модуль выключен.

Для каждой панели нужно определить, сколько световых модулей у неё включено.

Формат входных данных

В единственной строке записано одно целое число n.

Формат выходных данных

Выведите n + 1 чисел: для каждой панели с номером от 0 до n количество единиц в двоичной записи её номера.

Ограничения

• 0 <= n <= 10^5

Пример 1

Входные данные

2

Выходные данные

0 1 1

Пример 2

Входные данные

5

Выходные данные

0 1 1 2 1 2