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.