题目描述

给定方程 $x \oplus 3x = 2x$ ，给定正整数 $n$。

1. 求出所有小于等于 $n$ 的正整数中有多少个数满足该方程。

2. 求出所有小于等于 $2^n$ 的正整数中有多少个数满足该方程，对 $10^9 + 7$ 取模。

输入格式

第一行一个正整数 $T$，表示数据组数据。

接下来 $T$ 行 每行一个正整数 $n$。

输出格式

总共 $2\times T$ 行，第 $2 \times i - 1$ 行表示第 $i$ 组数据第一个询问的答案，第 $2 \times i$ 行表示第 $i$ 组数据第二个询问的答案。

1
1

1
2

数据规模与约定

对于 $100\%$ 的数据满足，$n \leq 10^{18}$。