#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = LLONG_MAX / 4;
#define rep(i, a, b) for(ll i = a; i < b; i++)
#define all(a) begin(a), end(a)
ll sz(auto& a) { return size(a); }
template<class T> bool chmin(T& a, T b) { if(a <= b) return 0; a = b; return 1; }
template<class T> bool chmax(T& a, T b) { if(a >= b) return 0; a = b; return 1; }

ll solve() {
    string S;
    cin >> S;
    ranges::reverse(S);
    for(char& c : S) c -= '0';
    const ll N = sz(S);
    if(S[0] == 0) {
        rep(i, 0, N) {
            if(S[i] == 1) {
                S[i]--;
                break;
            }
            else S[i]++;
        }
    }
    vector<ll> dp(1 << 19);
    dp[0] = 1;
    for(ll i = N; --i; ) {
        vector<ll> dp2(1 << 19);
        rep(bit, 0, 1 << 19) if(const ll x = dp[bit]; x) {
            { // add 0
                ll bit2 = bit;
                if(S[i] == 1) bit2 |= 1 << 18;
                dp2[bit2] += x;
            }
            if(bit & 1 << 18 || S[i] == 1) { // add 1
                ll bit2 = bit;
                const ll one = 1 << (i % 6 * 3), mask = 7 << (i % 6 * 3);
                bit2 += one;
                if((bit2 & mask) == mask) bit2 &= ~mask;
                dp2[bit2] += x;
            }
        }
        dp.swap(dp2);
    }

    {
        vector<ll> dp2(1 << 18);
        rep(bit, 0, 1 << 19) if(const ll x = dp[bit]; x) {
            { // add 1
                ll bit2 = bit & 0x3ffff;
                const ll one = 1, mask = 7;
                bit2 += one;
                if((bit2 & mask) == mask) bit2 &= ~mask;
                dp2[bit2] += x;
            }
        }
        dp.swap(dp2);
    }

    ll ans = 0;
    rep(bit, 0, 1 << 18) if(const ll x = dp[bit]; x) {
        vector<ll> X(6);
        rep(i, 0, 6) X[i] = (bit >> i * 3) & 7;
        if([&]() -> bool {
            rep(b, 1, 7) {
                ll sum = 0;
                for(ll i = 6; i--; ) sum = sum * b + X[i];
                if(sum % 7 == 0) return 0;
            }
            return 1;
        }()) ans += x;
    }
    return ans;
}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    ll T;
    cin >> T;
    while(T--) cout << solve() << endl;
}