10
4 108 114
5 30 155
8 193 197
9 71 169
2 163 166
8 120 144
8 22 151
4 21 166
2 46 127
8 38 51
 20
9 142 172
7 132 256
8 245 315
9 496 496
3 345 362
8 13 162
5 342 470
9 16 488
9 467 482
4 471 478
10 92 224
6 228 261
9 54 167
2 402 409
5 9 10
7 225 360
3 438 483
6 252 342
3 491 493
6 296 367
 1
8 1234567890123 123456789012345

0
3
0
1
3
0
5
16
9
1
 0
0
0
0
4
6
13
7
0
0
1
2
3
0
0
2
12
9
1
4
 774752389568

#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
#define ll long long 
ll dp[9][61][60006];
int d[65];
int judge(int n, int base)
{
	for (int i = 0;i < base;i++)
	{
		if (n % 3 == 1) return 0;
		n /= 3;
	}
	return 1;
}
int change(int s, int n)
{
	int a = s, b = n;
	while (b--) a /= 3;
	if (a % 3 < 2) s += pow(3.0, n);
	else s -= pow(3.0, n);
	return s;
}
ll dfs(int len, int num, int flag, int base)
{
	if (len < 0) return judge(num, base);
	if (!flag&&dp[base - 2][len][num] != -1) return dp[base - 2][len][num];
	int k = flag ? d[len] : (base - 1);
	ll ans = 0;
	for (int i = 0;i <= k;i++)
		ans += dfs(len - 1, num == 0 && i == 0 ? 0 : change(num, i), flag&&i == k, base);
	if (!flag) dp[base - 2][len][num] = ans;
	return ans;
}
ll solve(ll n, int base)
{
	int len = 0;
	while (n) d[len++] = n % base, n /= base;
	return dfs(len - 1, 0, 1, base);
}
int main()
{
	int n, i, j, k, sum, q, p;
	ll a, b;
	memset(dp, -1, sizeof(dp));
	scanf("%d", &q);
	while (q--)
	{
		scanf("%d%lld%lld", &p, &a, &b);
		printf("%lld\n", (solve(b, p) - solve(a - 1, p)));
	}
	return 0;
}