← 返回题目列表

Codeforces · 2086/E

E. 斑马状数字

中文机器翻译题面 查看原题

我们称正整数 斑马状 如果其二进制表示形式具有直到最高有效位的交替位,并且最低有效位等于 $$$1$$$。例如,数字 $$$1$$$、$$$5$$$ 和 $$$21$$$ 是 斑马状,因为它们的二进制表示 $$$1$$$、$$$101$$$ 和 $$$10101$$$ 满足要求,而数字 $$$10$$$ 不满足要求 斑马状,因为其二进制表示 $$$1010$$$ 的最低有效位是 $$$0$$$。

我们定义 斑马线值 正整数 $$$e$$$ 作为最小整数 $$$p$$$,使得 $$$e$$$ 可以表示为 $$$p$$$ 的总和 斑马状 数字(可能相同,也可能不同)

给定三个整数 $$$l$$$、$$$r$$$ 和 $$$k$$$,计算整数 $$$x$$$ 的数量,使得 $$$l \le x \le r$$$ 和 $$$x$$$ 的 斑马线值 等于 $$$k$$$。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的唯一行包含三个整数 $$$l$$$、$$$r$$$ ($$$1 \le l \le r \le 10^{18}$$$) 和 $$$k$$$ ($$$1 \le k \le 10^{18}$$$)。

输出

对于每个测试用例,输出一个整数 - $$$[l, r]$$$ 中的整数个数 斑马线值 $$$k$$$。

示例

输入
复制

5
1 100 3
1 1 1
15 77 2
2 10 100
1234567 123456789101112131 12

输出
复制

13
1
3
0
4246658701

注意

在第一个测试用例中,有 $$$13$$$ 合适的数字:$$$3, 7, 11, 15, 23, 27, 31, 43, 47, 63, 87, 91, 95$$$。

它们中的每一个都可以表示为 $$$3$$$ 的总和 斑马状 数字。