Назовем натуральное число почти простым, если оно раскладывается на произведение каких-нибудь двух неравных простых.

У нас есть две кучки камней, изначально в каждой по одному камню. За один ход можно добавлять один камень в одну из кучек, если в ней меньше N камней. Игра заканчивается, когда в обеих кучках будет N камней.

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

Например, если в первой кучке 12 камней, а во второй – 7, то позиция хорошая, т.к. число 127 простое.

Ваша задача найти такую последовательность ходов, при которой можно перейти из начальной позиции (1, 1) в конечную (N, N) через максимально возможное число хороших позиций. Например, для N = 4 одна из искомых последовательностей такова: 1; 1 -> 2; 1 -> 3; 1 -> 4; 1 -> 4; 2 -> 4; 3 -> 4; 4

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

Главный режиссер шоу, посвященного открытию ACM Programming Contest, хочет, чтобы участники шоу могли выстраиваться в различное число колонн ровно N способами. Причем при любом перестроении количество людей в каждой из колонн должно быть одинаковым. Требуется сообщить режиссеру, какое минимальное число М человек ему для этого понадобится. Так, при N = 3 потребуется пригласить всего М = 4 человек, которые могут выстроиться в 1, 2 и 4 колонны. Если же при некотором N для шоу потребуется более 10 ⁹ человек, то режиссеру можно сообщить, что подходящее число людей собрать невозможно.