你相信龙吗？想象一下，其中一条龙在深夜把你叫醒，问了你以下问题：

考虑正整数序列 $a = (a_1, a_2, \dots, a_k)$。

令 $f(a, x)$ 为 $x$ 在 $a$ 中出现的次数。例如，$f((1, 4, 1, 1), 1) = 3$。

令 $c(y)$ 为 $y$ 的二进制表示中 $1$ 的个数。例如，$c(13) = c(1101_2) = 3$。

令 $b(a) = \sum_{i \in a} c(f(a, i))$。例如，$b((1, 4, 1, 1)) = c(3) + c(1) = 2 + 1 = 3$。

对于给定的 $n$，求所有满足 $\sum_{i=1}^k a_i = n$ 的序列中 $b(a)$ 的最大值。

你会如何回答？

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 10^3$)，表示测试用例的数量。

接下来的 $t$ 行，每行包含一个整数 $n$ ($1 \le n \le 10^{18}$)。

输出格式

对于每个测试用例，按输入顺序输出一个整数，即问题的答案。

样例

输入 1

2
7
42

输出 1

3
10

说明

在第一个样例测试用例中，一个满足 $b(a) = 3$ 的序列是 $a = (1, 4, 1, 1)$。