In a country of n cities, numbered from \textbf{1} to \textbf{n}. The traveler is at the beginning of a town and wants to visit all the cities. We know that he acts according to the following algorithm: first, randomly chosen integer \textbf{m} in the interval \[\textbf{1}, \textbf{n--1}\]. After that the city visited in the order of \textbf{1}, \textbf{1 + m mod n}, \textbf{1 + (2·m) mod n}, ... and so on, until it gets to an already visited the city. Note that this process will always be finite, since the number of cities of course. Find the probability that the traveler will visit all the cities of the country. \InputFile The first line of the input file contains the number of test cases, \textbf{t} (\textbf{1} ≤ \textbf{t} ≤ \textbf{10000}). Each test consists of one line containing the number \textbf{n} (\textbf{2} ≤ \textbf{n} ≤ \textbf{2·10^9} ). \OutputFile For each test case output the answer to the problem as an irreducible fraction.