题目描述

2026 丙午马年，某赛马场举办一场盛大的赛马会，共有编号 \(1\) 到 \(n\) 的 \(n\) 匹骏马参赛。

对于每一对骏马 \(\left(l, r\right)\) （\(1 \le l \le r \le n\)），裁判组以 \(\lfloor \log_2 (\frac{r}{l}) \rfloor\) 来衡量二者的驰力差。请你计算所有骏马对的驰力差之和，即 \(\sum_{l = 1}^{n} \sum_{r = l}^{n} \lfloor \log_2 (\frac{r}{l}) \rfloor\)。

输入格式

本题有多组测试数据。输入 \(T\ (1 \le T \le 5 \times 10^4)\)，表示数据组数。

接下来 \(T\) 行，每行输入一个数 \(n\ (1 \le n \le 10^{9})\)。

输出格式

对于每组数据，输出答案。

样例输入

10
1
2
3
4
5
6
7
8
9
10

样例输出

0
1
2
5
8
12
16
23
30
38