CF855E.Salazar Slytherin's Locket

Harry came to know from Dumbledore that Salazar Slytherin's locket is a horcrux. This locket was present earlier at 12 Grimmauld Place, the home of Sirius Black's mother. It was stolen from there and is now present in the Ministry of Magic in the office of Dolorous Umbridge, Harry's former Defense Against the Dark Arts teacher.

Harry, Ron and Hermione are infiltrating the Ministry. Upon reaching Umbridge's office, they observed a code lock with a puzzle asking them to calculate count of magic numbers between two integers l and r (both inclusive).

Harry remembered from his detention time with Umbridge that she defined a magic number as a number which when converted to a given base b, all the digits from 0 to b - 1 appear even number of times in its representation without any leading zeros.

You have to answer q queries to unlock the office. Each query has three integers b__i, l__i and r__i, the base and the range for which you have to find the count of magic numbers.

哈利从邓布利多那里得知，萨拉查·斯莱特林的挂坠盒是一件魂器。这个挂坠盒原先存放在小天狼星·布莱克母亲的住所——格里莫广场12号。它后来从那里被盗走，如今被安置在魔法部多洛雷斯·乌姆里奇的办公室内；乌姆里奇曾是哈利的黑魔法防御术课教师。

哈利、罗恩和赫敏正潜入魔法部。当他们抵达乌姆里奇的办公室时，发现了一把带谜题的密码锁，要求他们计算区间 $[l, r]$（含端点）内“魔法数字”的个数。

哈利回想起自己曾因受罚而在乌姆里奇办公室抄写句子，她当时定义“魔法数字”为：将该数转换为给定进制 $b$ 后，其表示中（不含前导零）每一位数字 $0$ 至 $b-1$ 均恰好出现偶数次。

为打开办公室大门，你需要回答 $q$ 个查询。每个查询包含三个整数 $b_i$、$l_i$ 和 $r_i$，分别表示进制以及需要统计魔法数字个数的区间范围。

First line of input contains q (1 ≤ q ≤ 105) — number of queries.

Each of the next q lines contain three space separated integers b__i, l__i, r__i (2 ≤ b__i ≤ 10, 1 ≤ l__i ≤ r__i ≤ 1018).

输入的第一行包含一个整数 $q$（$1 \leq q \leq 10^5$），表示查询次数。

接下来的 $q$ 行，每行包含三个以空格分隔的整数 $b_i$、$l_i$、$r_i$（$2 \leq b_i \leq 10$，$1 \leq l_i \leq r_i \leq 10^{18}$）。

You have to output q lines, each containing a single integer, the answer to the corresponding query.

你需要输出 q 行，每行包含一个整数，即对应查询的答案。

In sample test case 1, for first query, when we convert numbers 4 to 9 into base 2, we get:

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

Out of these, only base 2 representation of 9 has even number of 1 and 0. Thus, the answer is 1.

在样例测试用例 1 中，对于第一个查询，当我们将数字 4 到 9 转换为二进制（基为 2）时，得到：

• 4 = 100₂,
• 5 = 101₂,
• 6 = 110₂,
• 7 = 111₂,
• 8 = 1000₂,
• 9 = 1001₂.

在这些数中，仅有 9 的二进制表示中 1 和 0 的个数均为偶数。因此，答案为 1。