Le postulat de Bertrand

Le postulat de Bertrand est un théorème qui affirme que pour tout entier n > 1, il existe au moins un nombre premier p compris entre n et 2n .

On vous propose un défi plus avancé : étant donné un nombre n, il s’agit de déterminer combien de nombres premiers p satisfont n < p < 2n.

Entrée

La première ligne de l’entrée contient un entier t (1 ≤ t ≤ 100), qui représente le nombre de jeux de test.

Les t lignes suivantes contiennent chacune un entier n (2 ≤ n ≤ 500 000).

Sortie

Pour chaque jeu de test, le programme doit afficher le nombre de nombres premiers compris entre n et 2n, chaque résultat sur une ligne distincte.

Exemples