#include<cstdio>
#include<cstring>
#include<queue>
#define MOD 1000000009
#define MAXN 2010
#define MAXM 210
using namespace std;
struct Trie {
	bool end;
	int fail, next[2];
	void Init() {
		end = false;
		fail = next[0] = next[1] = 0;
	}
};
Trie tree[MAXN];
int size, bcd[MAXN][10], digit[MAXM], dp[MAXN][MAXM];
char str[MAXM];
void Insert(char *s) {
	int now, t;
	for (now = 0; *s; s++) {
		t = *s - '0';
		if (!tree[now].next[t]) {
			tree[++size].Init();
			tree[now].next[t] = size;
		}
		now = tree[now].next[t];
	}
	tree[now].end = true;
}
void BFS() {
	int now, i, p;
	queue<int> q;
	q.push(0);
	while (!q.empty()) {
		now = q.front();
		q.pop();
		for (i = 0; i < 2; i++) {
			if (tree[now].next[i]) {
				p = tree[now].next[i];
				q.push(p);
				if (now) {
					tree[p].fail = tree[tree[now].fail].next[i];
					tree[p].end |= tree[tree[p].fail].end;
				}
			} else
				tree[now].next[i] = tree[tree[now].fail].next[i];
		}
	}
}
int NEXT(int now, int val) {
	if (tree[now].end)
		return -1;
	int i;
	for (i = 3; i >= 0; i--) {
		now = tree[now].next[val & (1 << i)];
		if (tree[now].end)
			return -1;
	}
	return now;
}
void BCD() {
	int i, j;
	for (i = 0; i <= size; i++) {
		for (j = 0; j < 10; j++)
			bcd[i][j] = NEXT(i, j);
	}
}
int DFS(int rt, int pos, bool bound, bool zero) {
	if (pos < 0)
		return 1;
	if (!bound && dp[rt][pos] != -1)
		return dp[rt][pos];
	int i, limit, ans;
	ans = 0;
	limit = bound ? digit[pos] : 9;
	if (zero && pos) {
		ans += DFS(rt, pos - 1, bound && limit == 0, true);
		if (ans >= MOD)
			ans -= MOD;
	} else {
		if (bcd[rt][0] != -1) {
			ans += DFS(bcd[rt][0], pos - 1, bound && limit == 0, false);
			if (ans >= MOD)
				ans -= MOD;
		}
	}
	for (i = 1; i <= limit; i++) {
		if (bcd[rt][i] != -1) {
			ans += DFS(bcd[rt][i], pos - 1, bound && i == limit, false);
			if (ans >= MOD)
				ans -= MOD;
		}
	}
	if (!bound)
		dp[rt][pos] = ans;
	return ans;
}
int DoIt() {
	int i, len;
	len = strlen(str);
	for (i = 0; i < len; i++)
		digit[len - i - 1] = str[i] - '0';
	return DFS(0, len - 1, true, true);
}
int main() {
	int c, n, i, len, ans;
	scanf("%d", &c);
	memset(dp, -1, sizeof(dp));
	while (c--) {
		scanf("%d", &n);
		tree[0].Init();
		for (size = 0; n--;) {
			scanf(" %s", str);
			Insert(str);
		}
		BFS();
		BCD();
		scanf(" %s", str);
		len = strlen(str);
		for (i = len - 1; i >= 0; i--) {
			if (str[i] > '0') {
				str[i]--;
				break;
			} else
				str[i] = '9';
		}
		ans = -DoIt();
		scanf(" %s", str);
		ans += DoIt();
		printf("%d\n", ans);
	}
	return 0;
}