我的数组写法到 $t= 10^4$ 就 Tle了，而且我还加优化了。呃呃呃

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
template < typename T > void read(T &x) {
	x = 0; char s = getchar(); bool f = 0;
	while (! isdigit(s)) { f |= s == '-'; s = getchar(); }
	while (  isdigit(s)) { x = x * 10 + s - 48; s = getchar(); }
	x = f ? -x : x;
}

const int MAXN = 1e2 + 7;

int A[MAXN];

struct Node {
	int x, lim, ze, st;
	Node (int x = 0, int lim = 0, int ze = 0, int st = 0) : x(x), lim(lim), ze(ze), st(st) {}
	bool operator < (const Node other) const {
		if (x == other.x) {
			if (lim == other.lim) {
				if (ze == other.ze) {
					return st < other.st;
				}
				return ze < other.ze;
			}
			return lim < other.lim;
		}
		return x < other.x;
	}
};

map < Node , int > f, g;

int Solve(int b, int x) {
	int len = 0, a = x;
	while (a) {
		A[++ len] = a % b; a = a / b;
	}
	reverse(A + 1, A + 1 + len);
	f.clear(); f[Node{0, 1, 1, 0}] = 1;
	for (int i = 0; i < len; i ++) {
		for (auto now : f) {
			int j = now.first.x, lim = now.first.lim, ze = now.first.ze, st = now.first.st;
			for (int k = 0; k < b; k ++) {
				if (ze && j != 0) continue;
				if (lim && k > A[i + 1]) continue;
				int lim_ = lim & (k == A[i + 1]);
				int ze_ = ze & !k;
				int st_	 = 0;
				if (ze_) st_ = st;
				else st_ = st ^ (1 << k);
				g[Node{k, lim_, ze_, st_}] += now.second;
			}
		}
		f = g; g.clear();
	}
	int ans = 0;
	for (int i = 0; i < b; i ++) {
		ans += f[{i, 0, 0, 0}] + f[{i, 0, 1, 0}] + f[{i, 1, 0, 0}] + f[{i, 1, 1, 0}];
	}
	return ans;
}

int main () {
	int T; read(T);
	while (T --) {
		int b, l, r; read(b); read(l); read(r);
		cout << Solve(b, r) - Solve(b ,l - 1) << '\n';
	}
	return 0;
}