Дядюшка Скрудж изготовил множество золотых слитков и пронумеровал их последовательностями из нулей и единиц длины 2n - 2 (номер каждого слитка выбит на нём). Известно, что

1. Любые два слитка имеют различные номера.
2. В номере любого из слитков не встречается двух нулей подряд.
3. Для любой последовательности, отвечающей свойству 2, слиток с таким номером есть в коллекции дядюшки Скруджа.

Затем дядюшка Скрудж решил разложить слитки по сейфам. Коды к сейфам подобраны схожим образом с номерами слитков. А именно

1. Код к сейфу является последовательностью из нулей и единиц длины n - 2.
2. Коды к любым двум сейфам различаются.
3. В коде ни одного из сейфов не встречается двух нулей подряд.
4. Для любого кода, отвечающего свойствам 1 и 3, сейф с таким кодом стоит в хранилище дядюшки Скруджа.

Дядюшка Скрудж положил в каждый из сейфов одинаковое количество золотых слитков, а оставшиеся слитки (их осталось меньше, чем сейфов) решил отправить на благотворительность. Найдите, сколько слитков лежит в каждом из сейфов дядюшки Скруджа.

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

Целое число n (3 ≤ n ≤ 70000).

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

Выведите количество слитков в каждом из сейфов.