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