Игра со спичками

На столе лежит кучка из N спичек. Двое играют в такую игру. За один ход разрешается взять из кучки одну, две или три спички, так чтобы оставшееся количество спичек не было простым числом (Например, можно оставить в кучке 1 или 4 спички, но нельзя оставить 2 или 3). Выигрывает тот, кто забирает последнюю спичку. Требуется определить, кто из игроков имеет выигрышную стратегию.

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

Вводится одно число N (1<=N<=10000).

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

Выведите число 1, если выигрышую стратегию имеет начинающий игрок, или число 2, если выигрышную стратегию имеет второй игрок.

Примеры
Входные данные
1
Выходные данные
1

Задача на informatics