Дистанционный практикум по программированию

Имеются гири с массами: 1 г, 2 г, ..., N г. Написать программу, распределяющую эти гири на максимально возможное количество пар так, чтобы суммарный вес гирь в каждой паре выражался простым числом.

Входные данные:
Натуральное число N (N ≤ 500000).

Выходные данные:
Выведите найденные пары.

Пример:
Ввод
7
Вывод
1 6
7 4
5 2