Аня и Боря играют в игру. Первый ход делает Аня. Изначально на доске записано натуральное число n. На каждом ходе игрока, этот игрок делает следующий ход:
- выбирает любое
x, не равное n, но кратное числу n (более формально 0 < x < n и n % x == 0)
- заменяет число
n на доске на n-x.
Если игрок не может сделать ход, то он проигрывает игру.
Определите, кто победит в этой игре, если оба будут следовать оптимальной стратегии.
Формат входных данных
Программа получает на вход натуральное число n (n <= 1000).
Формат выходных данных
Выведите 1, если Аня выигрывает игру, иначе выведите 0.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
10
|
1
|