题目内容

港区栈桥上有一排灯柱，从迎海端起依次编号为 $1,2,\ldots,p$。巡检员必须从 1 号灯柱走到 $p$ 号灯柱，且只能沿着相邻灯柱之间的光缆前进。台账规定：连接 $i$ 与 $i+1$ 的那根光缆，权值等于两端编号的按位异或 $i \oplus (i+1)$。巡检结束后要把这条路上所有光缆权值加起来，再对 1000000007 取模，作为当日巡检积分。

按位异或 $\oplus$ 按二进制逐位比较：该位两个数不同则结果为 1，相同则为 0。例如 $5=101_2$、$6=110_2$，则 $5 \oplus 6 = 011_2 = 3$。

形式化地，答案等于

当 $p=1$ 时路上没有光缆，答案为 0。

现在给出 q 个栈桥长度 $p$，请对每个 $p$ 分别求出巡检积分。

约束：

• 1 $\le$ $q$ $\le$ 200000
• 1 $\le$ $p$ $\le$ 1000000000000000000

输入描述

第一行一个整数 $q$（1 $\le$ $q$ $\le$ 200000），表示随后有多少个栈桥长度。

接下来 $q$ 行，每行一个整数 $p$（1 $\le$ $p$ $\le$ 1000000000000000000），表示灯柱编号的最大值。

输出描述

输出 $q$ 行，每行一个整数，即对应栈桥的巡检积分。

样例1

输入

3
5
8
7

输出

12
31
16

说明

• $p=5$：$1\oplus 2=3$，$2\oplus 3=1$，$3\oplus 4=7$，$4\oplus 5=1$，和为 12。
• $p=8$：在上一问基础上再加 $5\oplus 6=3$、$6\oplus 7=1$、$7\oplus 8=15$，和为 31。
• $p=7$：比 $p=8$ 少最后一项 15，和为 16。

样例2

输入

2
16
4

输出

79
11

说明

• $p=16$ 的权值和为 79。
• $p=4$：$1\oplus 2=3$，$2\oplus 3=1$，$3\oplus 4=7$，和为 11。

样例3

输入

1
100

输出

651

说明

$p=100$ 时整段权值和为 651，对 1000000007 取模后仍是 651。