我们称正整数 斑马状 如果其二进制表示形式具有直到最高有效位的交替位,并且最低有效位等于 $$$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$$$。
示例
输入复制
51 100 31 1 115 77 22 10 1001234567 123456789101112131 12
输出复制
13 1 3 0 4246658701
注意
在第一个测试用例中,有 $$$13$$$ 合适的数字:$$$3, 7, 11, 15, 23, 27, 31, 43, 47, 63, 87, 91, 95$$$。
它们中的每一个都可以表示为 $$$3$$$ 的总和 斑马状 数字。