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

В единственной строке находится целое положительное число N, не превосходящее 10²⁵⁰.

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