В этой задаче мы вспомним великого математика Леонарда Эйлера (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 ≤ 1010).

Выходные данные

Ваша программа должна вывести ответы на заданные примеры. Для каждого теста следует вывести две строки. Первая строка должна содержать количество решений уравнения. Вторая строка должна содержать все решения, перечисленные в порядке возрастания. Если уравнение не имеет решения, то для соответствующего теста вторая строка должна быть пустой.