#include <iostream>#include <stdio.h>#include <string.h>#include <algorithm>#include <queue>using namespace std;struct Trie{int next[2010][2],fail[2010];bool end[2010];int root,L;int newnode(){for(int i = 0;i < 2;i++)next[L][i] = -1;end[L++] = false;return L-1;}void init(){L = 0;root = newnode();}void insert(char buf[]){int len = strlen(buf);int now = root;for(int i = 0;i < len ;i++){if(next[now][buf[i]-'0'] == -1)next[now][buf[i]-'0'] = newnode();now = next[now][buf[i]-'0'];}end[now] = true;}void build(){queue<int>Q;fail[root] = root;for(int i = 0;i < 2;i++)if(next[root][i] == -1)next[root][i] = root;else{fail[next[root][i]] = root;Q.push(next[root][i]);}while(!Q.empty()){int now = Q.front();Q.pop();if(end[fail[now]])end[now] = true;for(int i = 0;i < 2;i++)if(next[now][i] == -1)next[now][i] = next[fail[now]][i];else{fail[next[now][i]] = next[fail[now]][i];Q.push(next[now][i]);}}}};Trie ac;int bcd[2010][10];int change(int pre,int num){if(ac.end[pre])return -1;int cur = pre;for(int i = 3;i >= 0;i--){if(ac.end[ac.next[cur][(num>>i)&1]])return -1;cur = ac.next[cur][(num>>i)&1];}return cur;}void pre_init(){for(int i = 0;i <ac.L;i++)for(int j = 0;j <10;j++)bcd[i][j] = change(i,j);}const int MOD = 1000000009;long long dp[210][2010];int bit[210];long long dfs(int pos,int s,bool flag,bool z){if(pos == -1)return 1;if(!flag && dp[pos][s]!=-1)return dp[pos][s];long long ans = 0;if(z){ans += dfs(pos-1,s,flag && bit[pos]==0,true);ans %= MOD;}else{if(bcd[s][0]!=-1)ans += dfs(pos-1,bcd[s][0],flag && bit[pos]==0,false);ans %= MOD;}int end = flag?bit[pos]:9;for(int i = 1;i<=end;i++){if(bcd[s][i]!=-1){ans += dfs(pos-1,bcd[s][i],flag&&i==end,false);ans %=MOD;}}if(!flag && !z)dp[pos][s] = ans;return ans;}long long calc(char s[]){int len = strlen(s);for(int i = 0;i < len;i++)bit[i] = s[len-1-i]-'0';return dfs(len-1,0,1,1);}char str[210];int main(){int T;scanf("%d",&T);int n;while(T--){ac.init();scanf("%d",&n);for(int i = 0;i < n;i++){scanf("%s",str);ac.insert(str);}ac.build();pre_init();memset(dp,-1,sizeof(dp));int ans = 0;scanf("%s",str);int len = strlen(str);for(int i = len -1;i >=0;i--){if(str[i]>'0'){str[i]--;break;}else str[i] = '9';}ans -= calc(str);ans %=MOD;scanf("%s",str);ans += calc(str);ans %=MOD;if(ans < 0)ans += MOD;printf("%dn",ans);}return 0;}
