Holodeck Hacking

#include <bits/stdc++.h>

int cnt[20];

void build_sums() {
    for(int i = 0; i <= 9; ++i) {
        for(int j = 0; j <= 9; ++j) {
            cnt[i + j]++;
        }
    }
}

long long count(long long val, long long pot, int first) {
    if(!pot and !val) return 1;
    if(val < 0 or val >= 20 * pot) return 0;
    if(pot == 1) return (val & 1) ^ 1;
    long long ans = 0;
    for(int s = val % 10; s < 20; s += 10) {
        ans += (cnt[s] - first) * count((val - s * pot - s) / 10, pot / 100, 0);
        first = 0;
    }
    return ans;
}

int main() {

    build_sums();
    int t;
    std::cin >> t;
    while(t--) {
        long long x;
        long long ans = 0;
        std::cin >> x;
        for(long long d = 1; d <= x + 1; d *= 10) {
            ans += count(x, d, 1);
        }
        std::cout << ans << std::endl;
    }
    return 0;
}