if (pos == -1) return 1;
if (dp[pos][ac][limit][zero] != -1)
return dp[pos][ac][limit][zero];
int sum = 0;
int tl,tz,end = limit digit[pos] : 9;
for (int i = 0; i <= end; ++i) {
tz = zero && i == 0;
tl = limit && (i == end);
if (tz == 1) {
sum = sum + Dfs(pos-1,0,tl,tz);
if (sum >= MOD) sum -= MOD;
continue;
}
if (next[ac][i] == -1) continue;
sum = sum + Dfs(pos-1,next[ac][i],tl,tz);
if (sum >= MOD) sum -= MOD;
}
dp[pos][ac][limit][zero] = sum;
return dp[pos][ac][limit][zero];
}
int Cal(char *num) {
int pos;
memset(dp,-1,sizeof(dp));
reverse(num,num+strlen(num));
for (pos = 0; num[pos]; ++pos)
digit[pos] = num[pos] - '0';
return Dfs(pos-1,0,1,1);
}
void Debug() {
for (int i = 0; i < total; ++i)
for (int j = 0; j <= 9; ++j)
printf("i = %d j = %d next = %d\n",i,j,next[i][j]);
}
void Subtoone(char *A) {
int len = strlen(A),i = len -1;
if (A[i] == 0) {
A[i] = '9';
while (A[i] == '0') i--;
}
A[i] = A[i] - '0' - 1 + '0';
}
int main()
{
int i,j,k,t;
scanf("%d",&t);
while (t--) {
scanf("%d",&n);
AC.Initial();
for (i = 1; i <= n; ++i) {
scanf("%s",str);
AC.Insert(str);
}
ans = 0;
AC.Build_AC();
AC.Cal_Next();
//AC.Debug();
scanf("%s",A);
Subtoone(A);
ans = ans - AC.Cal(A);
if (ans < 0) ans += MOD;
scanf("%s",B);
ans = ans + AC.Cal(B);
if (ans >= MOD) ans -= MOD;
printf("%d\n",ans);
}
}