描述

哈利从邓布利多那里得知，萨拉查·斯莱特林的挂坠是一个魂器。这个挂坠曾经在布莱克家族母亲的12号石茅阁中。它被盗走，现在在魔法部多洛雷斯·乌姆里奇的办公室中，乌姆里奇是哈利以前的黑魔法防御术教师。哈利、罗恩和赫敏正潜入魔法部。当他们到达乌姆里奇的办公室时，他们观察到一个带有谜题的密码锁，要求他们计算两个整数 $l$ 和 $r$ （包括两端）之间的魔法数字的数量。哈利回忆起在乌姆里奇的拘留时间，她定义了魔法数字为一个数字，当将其转换成给定的基数 $b$ 后，所有从 0 到 $b-1$ 的数字在其表示中出现的次数均为偶数次，并且没有前导零。你必须回答 $q$ 个查询以解锁办公室。每个查询有三个整数 $b_i$、$l_i$ 和 $r_i$，即基数和你需要找到魔法数字数量的范围。

输入规格

输入的第一行包含一个整数 $q$（$1 \leq q \leq 10^5$）—— 查询数量。接下来的每一行包含三个由空格分隔的整数 $b_i$、$l_i$ 和 $r_i$（$2 \leq b_i \leq 10$，$1 \leq l_i \leq r_i \leq 10^{18}$）。

输出规格

你必须输出 $q$ 行，每行包含一个整数，对应于相应查询的答案。

2
2 4 9
3 1 10

2
2 1 100
5 1 100

1
2

21
4

注释

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

• $4 = 100_2$，
• $5 = 101_2$，
• $6 = 110_2$，
• $7 = 111_2$，
• $8 = 1000_2$，
• $9 = 1001_2$。

在这些中，只有 $9$ 的二进制表示中 1 和 0 的数量是偶数。因此，答案是 1。