O PET (Patrulha Espacial da Terra) é uma organização responsável por proteger a Terra de invasões alienígenas a todo custo. Recentemente o PET interceptou mensagens interestelares desconhecidas em uma língua estranha, essas mensagens foram decifradas pelos agentes do PET e então foi descoberto que aliens de um planeta vizinho do planeta Terra pretendem lançar uma bomba para dizimar a humanidade.

Agentes do PET descobriram uma forma para desviar o curso da bomba para o sol e assim salvar a terra, entretanto para confirmar a mudança do curso da bomba é necessário inserir um código secreto que está relacionado com a quantidade de tempo que falta para a bomba atingir a Terra. Se faltam $N$ dias para bomba atingir a terra então o código é a quantidade de números $x$ tal que $(1 \leq x \leq N$ e $gcd(x, N) \neq 1)$. Você foi recrutado pelo PET para resolver esse problema, então dado a quantidade de dias restantes para a bomba destruir a Terra diga qual o código que o PET precisa inserir para desviar o curso da bomba e salvar toda a humanidade.

Entrada

A primeira linha da entrada contém um inteiro $T (1 \leq T\leq 10^5)$ indicando a quantidade de bombas que estão a caminho da Terra, nas próximas $T$ linhas contém cada uma um inteiro $N_i (1 \leq N_i \leq 10^6)$, que indica a quantidade de dias que faltam para a bomba $i 1(1 \leq i \leq T)$ atingir a Terra.

Saída

O seu programa deve imprimir $T$ inteiros, um para cada bomba com o código para que o PET possa salvar o mundo.