Подорож
У деякій країні n міст, пронумерованих від 1 до n. Мандрівник на початку знаходиться у 1 місті і хоче побувати в усіх містах країни. Відомо, що він діє за наступним алгоритмом: спочатку випадковим чином вибирається ціле число m з відрізку [1, n–1]. Після цього міста відвідуються у порядку 1, 1 + m mod n, 1 + (2·m) mod n, ... і так далі, доки не потрапить у вже відвідане місто. Відмітимо, що цей процес завжди буде скінченим, так як множина міст скінчена. Знайти ймовірність того, що мандрівник відвідає усі міста країни.
Вхідні дані
У першому рядку вхідного файлу задано кількість тестових випадків t (1 ≤ t ≤ 10000). Кожен тест складається з одного рядка, який містить число n (2 ≤ n ≤ 2·10^9 ).
Вихідні дані
Для кожного тесту виведіть відповідь до задачі у вигляді нескоротного дробу.