ベルトランの仮説

ベルトランの仮説は、n > 1 をみたす任意の整数 n について、n < p < 2nを満たす素数 p が必ず少なくとも一つは存在する、という定理です。

今回は、もう少し発展的な課題として、与えられた整数 n に対して、n < p < 2n を満たす素数 p が何個あるのかを答える問題を解いていただきます。

入力

入力の最初の行には、テストケースの数を示す単一の整数 t (1 ≤ t ≤ 100) が与えられます。

続く t 行それぞれに、単一の整数 n (2 ≤ n ≤ 500 000) が与えられます。

出力

各テストケースごとに、n < p < 2nを満たす素数 p の個数を 1 行ずつ出力してください。

例