НСД-визначник#3243
Вася нещодавно вивчив визначники і тепер хоче застосувати їх в галузі теорії чисел. Він склав матрицю n \times n, у якій у -ому рядку на місці стоїть число \text{НСД}(i, j). Наприклад, при n = 3 отримаємо визначник:
Тепер Васі потрібно обчислити значення визначника цієї матриці, але ця задача виявилась йому не під силу, і тепер Ви повинні розв'язати її. Так як визначник може виявитись достатньо великим, Вася просить порахувати його по модулю .
У першому рядку вхідного файлу міститься кількість тестів (1 \le t \le 100000). Кожен наступний рядок містить число – порядок визначника (1 \le n \le 10^9).
Для кожного тесту виведіть значення відповідного визначника по модулю .
Приклад 1