В этой задаче мы вспомним великого математика Леонарда Эйлера (1707 - 1783) и исследуем его хорошо известную функцию fi(n).
Значение fi(n) для натурального числа n равно количеству целых k (1 ≤ k ≤ n), взаимно простых с n. Два натуральных числа называются взаимно простыми если их наибольший общий делитель равен 1. Например fi(6) = 2, так как 1 и 5 взаимно простые с 6, в то время как 2, 3, 4 и 6 нет.
Задача Эйлера состоит в следующем: по заданному натуральному числу n найдите все натуральные числа x, удовлетворяющие уравнению: fi(x) = n.
Первая строка содержит количество тестов t (1 ≤ t ≤ 5). Далее следуют t строк, каждая из которых содержит одно натуральное число n (1 ≤ n ≤ 10^10
).
Ваша программа должна вывести ответы на заданные примеры. Для каждого теста следует вывести две строки. Первая строка должна содержать количество решений уравнения. Вторая строка должна содержать все решения, перечисленные в порядке возрастания. Если уравнение не имеет решения, то для соответствующего теста вторая строка должна быть пустой.