• Цифра на N-ом месте
  FIGURE ON A PLACE

В бесконечную бинарную последовательность выписаны натуральные числа по возрастанию в двоичном виде: 11011100101110111100010011010.... Определить, какая цифра стоит на N-ом месте.

Составьте программу FIGURE, определяющую эту цифру.

Технические требования:  

Входной файл: INPUT.TXT

Выходной файл: OUTPUT.TXT

Ограничение по времени тестирования: до 3 секунд на один тест

Входной файл: входной файл INPUT.TXT содержит натуральное число N (1≤N≤1000000000)

Выходной файл: выходной файл OUTPUT.TXT должен содержать найденную цифру.

Пример:

INPUT.TXT

5

OUTPUT.TXT

1