神奇数对

题目背景

Y同学是一位对数论和位运算的交织关系充满好奇的数学家。他最近发现了一类奇特的数对，其最大公约数（GCD）与按位异或（XOR）的值竟然完全相等。

为了深入研究这类“神奇数对”的分布规律，Y同学需要你编写一个程序，来快速统计在给定范围内，究竟隐藏着多少对这样的数。

题目描述

给定一个正整数 $N$。

你的任务是，计算有多少对整数 $(A, B)$ 同时满足以下所有条件：

1. $1 \le B \le A \le N$
2. $\gcd(A, B) = A \oplus B$

其中，$\gcd(A, B)$ 表示 $A$ 和 $B$ 的最大公约数，$\oplus$ 表示按位异或（XOR）操作。

你需要处理 $T$ 组独立的测试用例。

输入格式

输入的第一行包含一个整数 $T$，表示测试用例的数量。

接下来的 $T$ 行，每行包含一个整数 $N$，表示该组查询的范围上限。

输出格式

对于每组查询，输出一行，格式为 Case #i: ans，其中 i 是从 1 开始的测试用例编号，ans 是满足条件的数对数量。

样例

样例输入 1

2
7
20000000

样例输出 1

Case 1: 4
Case 2: 34866117

提示

样例 1 解释

对于 $N=7$，满足条件的数对 $(A, B)$ 有：

• (3, 2): $\gcd(3,2)=1$, $3 \oplus 2 = 1$
• (5, 4): $\gcd(5,4)=1$, $5 \oplus 4 = 1$
• (6, 4): $\gcd(6,4)=2$, $6 \oplus 4 = 2$
• (7, 6): $\gcd(7,6)=1$, $7 \oplus 6 = 1$ 共 4 对。

数据范围与约定

• $1 \le T \le 1000$
• $1 \le N \le 3 \times 10^7$