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