Description

小白和小蓝在一起上数学课, 下课后老师留了一道作业, 求下面这个数列的通项公式:\[ \begin{cases} A_{0} = 0\\ A_{1} = 1\\ A_{2i} = A_i & (i > 0)\\ A_{2i+1} = A_i + A_{i+1} & (i > 0) \end{cases} \] 小白作为一个数学爱好者, 很快就计算出了这个数列的通项公式. 于是, 小白告诉小蓝自己已经做出来了, 但为了防止小蓝抄作业, 小白并不想把公式公布出来. 于是小白为了向小蓝证明自己的确做出来了此题以达到其炫耀的目的, 想出了一个绝妙的方法: 即让小蓝说一个正整数 \(n\), 小白则说出的值, 如果当 \(n\) 很大时小白仍能很快的说出正确答案, 这就说明小白的确得到了公式. 但这个方法有一个很大的漏洞: 小蓝自己不会做, 没法验证小白的答案是否正确. 作为小蓝的好友, 你能帮帮小蓝吗?

Input

输入文件第一行有且只有一个正整数 \(T\), 表示测试数据的组数.

第 \(2 \sim T+1\) 行, 每行一个非负整数 \(n\).

Output

输出文件共包含 \(T\) 行.

第 \(i\) 行应包含一个不含多余前缀 \(0\) 的数, 它的值应等于 \(A_n\) (\(n\) 为输入数据中第 \(i+1\) 行被读入的整数)

Sample Input

3
1
3
10

Sample Output

1
2
3

Data Range

对于所有数据, 满足:\(T \leq 20, n \leq 10^{100}\).

Explanation

其实是一道考察选手的高精度能力的题目 (其实还有卡常), 但是自从 bzoj 兹磁了 Python 以后高精度瞬间变得人性化了~

如果单纯地模拟这个 dfs 过程复杂度会退化成 \(O(n)\), 需要一定记忆化搜索的技巧, 然后把搜索深度优化到 \(O(\log n)\), 整体时间复杂度趋近于 \(O(\log n \log \log n)\).

由于 xmcp 的一次血的教训, 我们发现了 bzoj 上部署的 Python 其实是 bzoj 限定版, 有一些关键的库经过修改.

例如用 Python 内置的记忆化搜索可以这样:

import functools
@functools.lru_cache(maxsize=None)
def dfs(n):
    if n <= 1: return n
    return dfs(n//2) + (dfs(n//2+1) if n%2!=0 else 0)
T = int(raw_input())
for i in range(0, T):
    print(dfs(int(raw_input())))

虽然看上去是一个十分优雅的写法, 但是其实会炸锅......

经过笔者亲身校验, Lemon, Cena, pyJudge, pyMatcher, defuz 等多枚著名评测系统均认定此程序与标准解法没有任何差别.

但是 bzoj 就是认为这是一个妥妥的 Wrong Answer......

于是 xmcp 把我的 AC 代码拷了过去, 但是仍然是 Wrong Answer......

结果删掉了 import functools 就过掉了, 这说明 bzoj 的 Python 可能是假的

另外下面的样例代码是不能过掉的, 需要去掉 raw_input = input, 这是用来兼容 Python 3 的 (请不要吐槽 Python 2)

Source Code


raw_input = input

T = int(raw_input())

mark = { 0: 0, 1: 1 }

def dfs(x):
    if x in mark:
        return mark[x]
    y = x // 2
    if x == y * 2:
        res = dfs(y)
    else:
        res = dfs(y) + dfs(y + 1)
    mark[x] = res
    return res

for idx in range(0, T):
    n = int(raw_input())
    res = dfs(n)
    print(res)