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

import java.util.Arrays;
import java.util.Scanner;
 
public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		dp = new Long[2][11][64][1<<10];
		int q = scan.nextInt();
		for(int qq = 0; qq < q; qq++) {
			b = scan.nextInt();
			long l = scan.nextLong()-1, r = scan.nextLong();	
			System.out.println(solve(r)-solve(l));
		}
	}
 
	static int b;
	static int[] num;
	static Long[][][][] dp;
 
	static long go(int at, int m, int mask, int z) {
		if(at == num.length) return mask==0&&z==1?1:0;
		if(dp[z][b][at][mask] != null && m == 0) return dp[z][b][at][mask];
		long res = 0;
		int lim = b-1;
		if(m == 1) lim = num[at];
		for(int i = 0; i <= lim; i++) {
			int nmask = mask;
			if(z == 1 || i != 0) nmask ^= 1<<i;
			res += go(at+1, i==num[at]?m:0, nmask, i!=0?1:z);
		}
		if(m == 0) dp[z][b][at][mask] = res;
		return res;
	}
 
	static long solve(long in) {
		char[] a = Long.toString(in, b).toCharArray();
		num = new int[64];
		for(int i = 64-a.length, j = 0; i < 64; i++, j++) num[i] = a[j]-'0';
		return go(0, 1, 0, 0);
	}
 
}