← 返回题目列表

Codeforces · 855/E

E. 萨拉查·斯莱特林的挂坠盒

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

哈利从邓布利多那里得知萨拉查·斯莱特林的挂坠盒是一个魂器。这个挂坠盒早些时候曾出现在格里莫广场 12 号,也就是小天狼星·布莱克的母亲的家中。它是从那里被盗的,现在存放在魔法部多洛洛斯·乌姆里奇(哈利的前黑魔法防御术老师)的办公室里。

哈利、罗恩和赫敏正在渗透到魔法部。到达乌姆里奇的办公室后,他们发现一个密码锁,上面有一个谜题,要求他们计算两个整数 l 和 r(两者都包含)之间的幻数计数。

哈利记得在乌姆里奇的拘留期间,她将幻数定义为一个数字,当转换为给定的基数 b 时,从 0 到 b - 1 的所有数字在其表示形式中出现偶数次,且没有任何前导零。

您必须回答 q 个问题才能解锁办公室。每个查询都有三个整数 bi、li 和 ri,即您必须找到幻数计数的基数和范围。

输入

输入的第一行包含 q (1 ≤ q ≤ 105) — 查询数。

接下来的 q 行包含三个空格分隔的整数 bi、li、ri (2 ≤ bi ≤ 10, 1 ≤ li ≤ ri ≤ 1018)。

输出

你必须输出 q 行,每行包含一个整数,即相应查询的答案。

示例

输入 #1

2
2 4 9
3 1 10

输出 #1

1
2

输入 #2

2
2 1 100
5 1 100

输出 #2

21
4

注意

在示例测试用例 1 中,对于第一个查询,当我们将数字 4 到 9 转换为基数 2 时,我们得到:

- 4 = 1002,
- 5 = 1012,
- 6 = 1102,
- 7 = 1112,
- 8 = 10002,
- 9 = 10012.

其中,只有以 2 为底的 9 的表示形式有偶数个 1 和 0。因此,答案是 1。