Jzzhu собрал n яблок с большого яблочного дерева. Он пронумеровал яблоки от 1 до n и теперь хочет продать их яблочному магазину.
Jzzhu собирается продавать уже упакованные яблоки. В каждой пачке должно быть по два яблока, а наибольший общий делитель номеров яблок в пачке должен быть больше 1. Какое максимальное количество пачек сможет получить Jzzhu, если будет следовать описанным условиям? Также он должен знать, как именно упаковать яблоки оптимальным способом. Помогите ему найти оптимальное распределение яблок по упаковкам.
Выходные данные
В первой строке выведите целое число m, обозначающее максимальное количество пачек, которые юноша сможет получить. В каждой из следующих m строк должно быть записано два целых числа — номера яблок в текущей пачке.
Естественно, что одно яблоко может находиться не более чем в одной пачке. Если существует несколько оптимальных ответов, разрешается вывести любой из них.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
|
2
6 3
2 4
|
|
2
|
9
|
3
9 3
2 4
6 8
|
|
3
|
2
|
0
|