Назовем треугольником Паскаля следующую числовую структуру. В первой строке стоят две единицы, а в последующих строках каждый элемент равен сумме двух вышестоящих над ним элементов.

Ваша задача найти наибольший общий делитель (НОД) элементов i-й строки, стоящих между единицами.

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

Задано единственное число i (1 < i < 2³¹).

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

Вывести НОД элементов.

3

3

4

2