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$$.