C. Palindrome Basis

#include <algorithm>
#include <bitset>
#include <map>
#include <vector>
#include <string>
#include <iostream>
#include <cmath>
#include <stack>
#include <set>
/*
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
*/
using namespace std;

const double eps = 1e-10;
const double pi = 3.1415926535897932384626433832795;
const double eln = 2.718281828459045235360287471352;

#define f(i, a, b) for (int i = a; i <= b; i++)
#define LL long long
#define IN freopen("in.txt", "r", stdin)
#define OUT freopen("out.txt", "w", stdout)
#define scan(x) scanf("%d", &x)
#define mp make_pair
#define pb push_back
#define sqr(x) (x) * (x)
#define pr1(x) printf("Case %d: ",x)
#define pn1(x) printf("Case %d:\n",x)
#define pr2(x) printf("Case #%d: ",x)
#define pn2(x) printf("Case #%d:\n",x)
#define lowbit(x) (x&(-x))

#define fi first
#define se second
#define sz(x) int((x).size())
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define summ(a) (accumulate(all(a), 0ll))

typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;

int dp[(int)1e5+9],tt,n;

int ck(int x){
    int aa=x,res=0;
    while(aa>0){
        res=res*10+aa%10;
        aa/=10;
    }
    return res==x;
}

vi v;
/*
int dfs(int ter,int now,int nl,int len){
    cout<<ter<<"::"<<now<<"\n";
    if(now==ter)return 1;
    int ans=0;
    for(int i=nl;i<len;++i){
        if(now+v[i]<=ter){
            ans+=dfs(ter,now+v[i],i,len);
        }
    }
    return ans;
}*/

const int mod=1e9+7;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int cnt=0;
    for(int i=1;i<=4e4;++i){
        if(ck(i))v.pb(i);
    }
    int len=v.size();
    dp[0]=1;
    for(int i=0;i<len;++i){
        for(int j=0;j<=4e4;++j){
            dp[j+v[i]]+=dp[j];
            dp[j+v[i]]%=mod;
        }
    }

    //f(i,1,30)cout<<i<<"::"<<dp[i]<<"\n";
    cin>>tt;
    f(sb,1,tt){
        cin>>n;
        cout<<dp[n]<<"\n";
    }
    return 0;
}

/*
 * ┌───┐┌───┐   ┌───┬───┬───┬───┐ ┌───┬───┬───┬───┐ ┌───┬───┬───┬───┐ ┌───┬───┬───┐  ┌──┐  ┌──┐  ┌──┐
 * │╠╣1││Esc│   │ F1│ F2│ F3│ F4│ │ F5│ F6│ F7│ F8│ │ F9│F10│F11│F12│ │P/S│S L│P/B│  │┌┐│  │┌┐│  │┌┐│
 * ├───┤└───┘   └───┴───┴───┴───┘ └───┴───┴───┴───┘ └───┴───┴───┴───┘ └───┴───┴───┘  └└┘┘  └└┘┘  └└┘┘
 * │╠╣2│┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───────┐ ┌───┬───┬───┐ ┌───┬───┬───┬───┐
 * └───┘│~ `│! 1│@ 2│# 3│$ 4│% 5│^ 6│& 7│* 8│( 9│) 0│_ -│+ =│ BacSp │ │Ins│Hom│PUp│ │Num│ / │ * │ - │
 * ┌───┐├───┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─────┤ ├───┼───┼───┤ ├───┼───┼───┼───┤
 * │╠╣3││ Tab │ Q │ W │ E │ R │ T │ Y │ U │ I │ O │ P │{ [│} ]│ | \ │ │Del│End│PDn│ │ 7 │ 8 │ 9 │   │
 * ├───┤├─────┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴─────┤ └───┴───┴───┘ ├───┼───┼───┤ + │
 * │╠╣4││ Caps │ A │ S │ D │ F │ G │ H │ J │ K │ L │: ;│" '│ Enter  │               │ 4 │ 5 │ 6 │   │
 * └───┘├──────┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴────────┤     ┌───┐     ├───┼───┼───┼───┤
 * ┌───┐│ Shift  │ Z │ X │ C │ V │ B │ N │ M │< ,│> .│? /│  Shift   │     │ ↑ │     │ 1 │ 2 │ 3 │   │
 * │╠╣5│├─────┬──┴─┬─┴──┬┴───┴───┴───┴───┴───┴──┬┴───┼───┴┬────┬────┤ ┌───┼───┼───┐ ├───┴───┼───┤ E││
 * ├───┤│ Ctrl│ Win│ Alt│         Space         │ Alt│ Win│Menu│Ctrl│ │ ← │ ↓ │ → │ │   0   │ . │←─┘│
 * │╠╣6│└─────┴────┴────┴───────────────────────┴────┴────┴────┴────┘ └───┴───┴───┘ └───────┴───┴───┘
 * └───┘
 */