Background

Special for beginners, ^_^

Description

给出一个整数 $n（1<n\le10^{18}）$，问存在多少个 $R$ ，将 $n$ 转换为 $R$ 进制后，看起来像一个二进制数。

Format

Input

第一行一个整数 $T（\le10^5）$，表示有 $T$ 组数据。

接下来 $T$ 行，每行一组数据 $n$ 。

Output

每行输出一组数据对应的答案。

Samples

3
2
8
16

1
3
4

Limitation

1s, 1024KiB for each test case.