Bertrands Postulat

Bertrands Postulat ist ein Theorem, das besagt, dass für jede ganze Zahl n > 1 immer mindestens eine Primzahl p existiert, die zwischen n und 2n liegt (n < p < 2n).

In diesem Zusammenhang sollen Sie eine anspruchsvollere Aufgabe lösen. Gegeben ist eine Zahl n, und Sie sollen Fragen beantworten wie beispielsweise: Wie viele Primzahlen p gibt es, für die n < p < 2n gilt?

Eingabe

Die erste Zeile der Eingabe enthält eine einzelne ganze Zahl t (1 ≤ t ≤ 100), die die Anzahl der Testfälle bestimmt.

Die nächsten t Zeilen enthalten jeweils eine ganze Zahl n (2 ≤ n ≤ 500 000).

Ausgabe

Das Programm soll für jeden Testfall in einer eigenen Zeile ausgeben, wie viele Primzahlen sich im Bereich zwischen n und 2n befinden.

Beispiele