A group of students from the \textbf{n} people gathered to celebrate a successful exam on algorithms. But the thing they forgot to buy the most important thing to celebrate - a birthday cake and now need to choose someone who goes to the store for a cake. Since wanting to do it voluntarily appeared, they decided to make a choice with the next game. In the plane draw a complete graph of \textbf{n} vertices, numbered from \textbf{1} to \textbf{n}, initially located in the first chip top. Each player must pass the chip to all vertices of the graph, visiting each only once and return to the starting position, each path can be passed only once per game (different routes are those which vary the order of the vertices). Those who can not build a road recognized by the game and goes for the cake. The boys walked on stage and it is known that the cake went to a player who went \textbf{n}^tm. Your task is to determine what the smallest number of children could be in a band, if you know that there were at least \textbf{m}. \InputFile The first line of the input file contains the number of tests \textbf{t} (\textbf{1} ≤ \textbf{t} ≤ \textbf{1000}). Each test consists of a single number \textbf{m} (\textbf{1} ≤ \textbf{m} ≤ \textbf{10^18}). \OutputFile For each test case output a single line only number that is the answer to the problem.