eolymp
bolt
Try our new interface for solving problems
Problems

Малая теорема Ферма

Малая теорема Ферма

Time limit 4 seconds
Memory limit 256 MiB

Малая теорема Ферма утверждает, что 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.

Input data

В первой строке входного файла задано натуральное число T (1T10^5) – количество тестов. В каждой из последующих T строк задано целое число n (2n2·10^6).

Output data

Для каждого числа n из входного файла выведите в отдельной строке ответ на задачу.

Examples

Input example #1
2
2
3
Output example #1
3
12