哈利从邓布利多那里得知萨拉查·斯莱特林的挂坠盒是一个魂器。这个挂坠盒早些时候曾出现在格里莫广场 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。