Número Mágico

Flúcio é um garoto muito interessado em problemas de matemática, recentemente viu um problema no Projeto Euler sobre divisores e ficou intrigado com o problema, então ele decidiu pedir sua ajuda.

O problema consiste em, dado um número $N$, calcule todos os inteiros $k$ de $1$ até $N$ de tal forma que $H(k)$ seja um quadrado perfeito.

A função $H(x)$ retorna a soma do quadrado dos divisores positivos do número $x$ excluindo ele mesmo.

Exemplo:

$H(1) = 0$ (Devido a exclusão do valor $1$)

$H(5) = 1^2 = 1$

$H(8) = 1^2 + 2^2 + 4^2 = 1 + 4 + 16 = 21$

Entrada

A primeira linha contém um inteiro $Q$.

As próximas $Q$ linhas contém um número inteiro, representando o $N$ da questão.

Saída

Para cada um dos $N$'s, responda o número de $k$'s de $1$ até $N$ tal que $H(k)$ seja um quadrado perfeito.

Restrições

• $1 \leq N \leq 10^6$
• $1 \leq Q \leq 10^6$

Exemplos

Entrada	Saída
3 5 10 516	4 5 103

 

 

 

 

No primeiro caso temos os números $1, 2, 3, 5$ e no segundo temos $1, 2, 3, 5, 7$.