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