В некоторой стране \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 Для каждого теста выведите ответ к задаче в виде несократимой дроби.