Мала теорема Ферма
Мала теорема Ферма стверджує, що 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 з вхідного файлу виведіть у окремому рядку відповідь до задачі.