Задача про дружественные числа

Назовём две несократимые дроби p/q и r/s дружественными, если |p-r| ⋅ |q-s|=2. Требуется выстроить все дроби, у которых числитель и знаменатель — целые положительные числа, не превосходящие N, в последовательность (возможно, с повторениями) таким образом, что любые две соседние дроби являются дружественными.

Формат ввода
Входные данные содержат одно целое число N (2 ≤ N ≤ 100).

Формат вывода
Если способа выстроить все несократимые дроби с числителями и знаменателями, строго большими 0 и не превосходящими N в ряд (возможно, с повторениями) так, чтобы любые две соседние дроби в этом ряду были дружественными, выведите -1. Иначе в первой строке выведите количество дробей в последовательности, а в следующей — сами дроби через пробел в формате a / b (то есть число и знак дроби обязательно разделять пробелом).

Если ответов несколько, разрешается вывести любой. Обратите внимание, что, хотя последовательность может не быть кратчайшей, длина последовательности не должна превышать 2 ⋅ 104.

Пример 1
Ввод Вывод
2
-1
Пример 2
Ввод Вывод
3
7
1 / 2 3 / 1 2 / 3 1 / 1 3 / 2 1 / 3 2 / 1

0