/*
    问A到B之间的所有整数，转换成BCD Code后，有多少个不包含属于给定非法01串集合的子串。 
    0 < A ≤ B < 10^200

    统计问题，这里我用之前的那种写法，还是比较方便的
    http://www.cppblog.com/Yuan/archive/2011/01/25/139299.html

    参考watashi的
    由于需要判定合不合法，需要构造ac自动机
    然后预处理下，将每一步01处理成每一步是走0..9，非法（即不可走的）指针就为-1了
    然后状态就是
    (root, pos, bound) 表示前面已经走到了节点root，当前要检查digit数组的第pos位，bound表示是否有上界，
    bound为false表示木有，即该位置可枚举0..9
    
    然后就是记忆化搜索了
    注意处理前置0，这里多加了一维，表示前缀是否都是0
*/
#include<iostream>
#include<cstring>
#include<map>
#include<algorithm>
#include<stack>
#include<queue>
#include<cmath>
#include<string>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<set>
#include<list>
#include<numeric>
#include<cassert>
#include<ctime>
#include<bitset>

using namespace std;


struct AhoCorasick {
    static const int UNDEF = 0;
    static const int MAXN = 2048;
    static const int CHARSET = 2;

    int end;
    int tag[MAXN];
    int fail[MAXN];
    int trie[MAXN][CHARSET];
    int next[MAXN][10];

    int newNode() {
        tag[end] = UNDEF;
        fill(trie[end], trie[end] + CHARSET, -1);
        return end ++;
    }

    void init() {
        end = 0;
        newNode();
    }
    
    void insert(int root, char *s) {
        if(*s == 0){
            tag[root] = 1;
            return;
        }
        if(trie[root][*s-'0'] == -1){
            trie[root][*s-'0'] = newNode();
        }
        insert(trie[root][*s-'0'], s+1);
    }
    
    void build() {
        queue<int> bfs;
        fail[0] = 0;
        for( int i = 0 ; i < CHARSET ; i ++) {
            if(trie[0][i] != -1){
                fail[trie[0][i]] = 0;
                bfs.push(trie[0][i]);
            } else {
                trie[0][i] = 0;
            }
        }
        while(!bfs.empty()) {
            int p = bfs.front();
            tag[p] |= tag[fail[p]]; //
            bfs.pop();
            for(int i = 0 ; i < CHARSET; i ++) {
                if (trie[p][i] != -1) {
                    fail[trie[p][i]] = trie[fail[p]][i];
                    bfs.push(trie[p][i]);
                } else {
                    trie[p][i] = trie[fail[p]][i];
                }
            }
        }
    }

    int calNext(int p , int x) {
        if(tag[p] == 1){
            return -1;
        }
        for(int i = 3; i >= 0 ; i --) {
            p = trie[p][(x>>i)&1];
            if(tag[p] == 1){
                return -1;
            }    
        }
        return p;
    }

    void calNext() {
        for( int i = 0 ; i < end ; i++) {
            for (int j = 0 ; j  <= 9 ; j++){
                next[i][j] = calNext(i,j);
            }
        }
    }
} ac;

const long long MOD = 1000000009LL;

long long dp[AhoCorasick::MAXN][250];//不是AhoCorasick.MAXN
int digit[250];

long long dfs(int root, int pos , bool bound, bool preIsZero) {
    if(pos == -1) {
        return 1LL;
    }
    if( dp[root][pos] != -1 && !bound){
        return dp[root][pos];
    }
    
    long long ans = 0;
    int end = bound ? digit[pos] : 9;

    //deal with zero
    if(preIsZero && pos > 0) {
        //该位仍是前缀0             下面这个也即为false了
        ans += dfs(root, pos - 1, bound && end == 0, true);    
    } else {
        if(ac.next[root][0] != -1 && ac.tag[ac.next[root][0]] == 0 ) {
            ans += dfs(ac.next[root][0], pos - 1, bound && end == 0, false);
        }
    }

    for(int i = 1; i <= end ; i ++ ) {
        if(ac.next[root][i] != -1 && ac.tag[ac.next[root][i]] == 0 ) {
            ans += dfs(ac.next[root][i], pos-1, bound && i == end, false);
        }
    }
    ans %= MOD;
    if(!bound) {
        dp[root][pos] = ans;
    }
    return ans;
}

long long gao(char *s) {//cal the legal number in [0,s]
    int len = strlen(s);
    for(int i = len - 1 ; i >= 0 ; i -- ){
        digit[len - 1 - i] = s[i] - '0';
    }
    return dfs(0, len-1, true, true);
}

int main() {

#ifndef ONLINE_JUDGE
    freopen("in","r",stdin);
#endif

    int T, n;
    char str[250] , *p;
    for (scanf("%d", &T); T--; ) {
        ac.init();
        for (scanf("%d", &n); n -- ; ) {
            scanf("%s", str);
            ac.insert(0, str);
        }
        ac.build();
        ac.calNext();

        memset(dp, -1, sizeof dp);
        
        long long ans = 0;
        //A
        p = str;
        scanf("%s", p);
        for (int i = strlen(p) - 1 ; i >= 0 ; i-- ){
            if(p[i] == '0'){
                p[i] = '9';
            } else {
                p[i] --;
                break;
            }
        }
        if(*p == '0' && *(p+1) != 0){
            p++;
        }
        ans -= gao(p);

        //B
        p = str;
        scanf("%s", p);
        ans += gao(p);

        printf("%lld\n", (ans+MOD)%MOD);
    }    
    return 0;
}