B: 自身の 2 倍

問題

クエリが Q 個与えられます。1 個のクエリにつき、 1 つの正の整数 N が与えられるので、次の 2 つの条件を満たす正の整数 M の個数を求めてください。

• 2 \leq M \leq N を満たす
• M の約数のうち、M を除いたものの総積が M の 2 倍以上になる

入力形式

入力は以下の形式で与えられます。

Q
N_1
N_2
:
N_Q

• 1 行目では、クエリ数 Q が与えられます。
• 2 行目から N+1 行目では、各クエリについて与えられる 1 つの正の整数 N が与えられます。

制約

• 1 \leq Q \leq 10^5
• 2 \leq N_i \leq 10^5 (1 \leq i \leq Q)

出力形式

上記の 2 つの条件を満たす正の整数の個数を、各 N_i に対して、改行区切りで出力してください。

入力例

3
43
9
24

出力例

11
0
5

• N=24 の時、M として考えられるのは 12, 16, 18, 20, 24 の 5 種類である。