Il postulato di Bertrand

Il postulato di Bertrand è un teorema che afferma che, per ogni intero n > 1, esiste sempre almeno un numero primo p compreso tra n e 2n .

Ti viene richiesto di risolvere un compito più impegnativo. Dato un numero n, devi rispondere a domande come quante volte compare un numero primo p tale che n < p < 2n.

Input

La prima riga dell’input contiene un unico intero t (1 ≤ t ≤ 100), che indica il numero di test case.

Le successive t righe contengono un singolo intero n (2 ≤ n ≤ 500 000).

Output

Il programma deve stampare il numero di numeri primi compresi tra n e 2n per ogni test case, ciascuno su una nuova riga.

Esempi