Рабочее место участника

В августе 2012 года японский математик Синити Мотидзуки опубликовал доказательство знаменитой ABC-гипотезы, которая была сформулирована в работах Массера и Эстерле в 80-х гг. XX века. Эта гипотеза оказалась весьма полезной при получении множество фундаментальных результатов теории чисел и алгебраической геометрии и, в частности, великая теорема Ферма может быть выведена в несколько строк как её следствие.

Для этой задачи необходимо понятие радикала. Радикалом числа `"rad"(n)` называется произведение всех простых множителей этого числа. Например, `"rad"(24)=2*3=6`. У этого числа есть несколько очевидных свойств. Например, если `a` и `b` взаимно просты, то есть не имеют общих делителей, отличных от единицы, то `"rad"("ab")\ =\ "rad"(a)*"rad"(b)`. Кроме этого, равенство `"rad"(a)=a` выполняется тогда и только тогда, когда `a` – произведение попарно различных простых чисел.

Рассмотрим тройки чисел `(a,\ b,\ c)`, для которых `a+b=c` и все три числа взаимно просты. Так как числа `a`, `b`, `c` взаимно просты, то `"rad"("abc")="rad"(a)*"rad"(b)*"rad"(c)`. Массера и Эстерле заинтересовал вопрос: какое из чисел `c` или `"rad"("abc")` больше? Оказалось, что однозначного ответа на этот вопрос нет. Например, для тройки `(2,\ 3,\ 5)` `"rad"(2*3*5)=2*3*5=30>5`, а для тройки `(1,\ 8,\ 9)` `"rad"(1*8*9)="rad"(23*32)=2*3=6<9`.

Дальнейшие исследования позволили установить, что тройки первого типа встречаются намного чаще: если взять случайную тройку, то почти всегда будет выполняться именно первое неравенство. Поэтому тройки, для которых `c>"rad"("abc")`, получили название исключительных. Удалось доказать, что таких троек бесконечно много, и даже построить бесконечную серию троек, у которой отношение `"rad"("abc")/c` стремится к 0.

Математикам удалось найти другое ограничение на возможные значения радикала, которое получило название "ABC-гипотеза": для любого действительного числа `r>1` существует конечное число троек натуральных чисел `(a,\ b,\ c)` таких, что для них выполняются одновременно три условия: `a+b=c`; `a`, `b` и `c` взаимно просты и `c>"rad"("abc")^r`.

Напишите программу для поиска исключительных троек, которая для заданного `c` находит все пары натуральных чисел `(a,\ b)`, таких что `a<b`, `a+b=c`, числа `a`, `b` и `c` взаимно просты (достаточно проверить взаимную простоту любой пары из этой тройки) и `"rad"("abc")<c`.

Первая строка ввода содержит натуральное число `c` (`2\ ≤\ c\ ≤\ 10^7`).

В первой строке вывести число `K` – количество найденных пар. Затем вывести `K` строк – найденные пары в порядке возрастания `a`.

9

1
1 8