Малая теорема Ферма
Малая теорема Ферма утверждает, что a^p-a делится на p для любого простого числа p и целого числа a. В данной задаче речь будет идти о чём-то похожем. А именно, для данного натурального числа n > 1 необходимо найти все натуральные m такие, что a^n-a делится на m для любого целого числа a. Например, для n = 2 существует 2 таких числа: 1 и 2, а для n = 3 существует 4 таких числа: 1, 2, 3 и 6. Так как таких чисел может быть много, то надо вывести сумму всех таких чисел по модулю 10^9+7. Гарантируется, что множество таких чисел конечно для любого n >1.
Входные данные
В первой строке входного файла задано натуральное число T (1 ≤ T ≤ 10^5) – количество тестов. В каждой из последующих T строк задано целое число n (2 ≤ n ≤ 2·10^6).
Выходные данные
Для каждого числа n из входного файла выведите в отдельной строке ответ на задачу.