Let \textbf{m} is certain natural number. A number \textbf{a} Є \{\textbf{0}, \textbf{1}, ..., \textbf{m}-\textbf{1}\} is called a quadratic residue modulo \textbf{m} if there exists an integer \textbf{x} such that \textbf{x^2}-\textbf{a} is divisible by \textbf{m}. You are given \textbf{m} and required to find the number of quadratic residues modulo \textbf{m}. \InputFile In the first line of input file you are given the number of test cases \textbf{T} ≤ \textbf{100}. Each of following \textbf{T} lines contains a number \textbf{m} for respective case. It is provided that all numbers does not exceed \textbf{10^12}. \OutputFile For each case you should output in a separate line the number of quadratic residues modulo \textbf{m}.