#include <iostream>
#include <fstream>
#include <cstring>
#include <algorithm>
#include <string>
#include <cstdio>
using namespace std;
char s[22];
long long int n;
long long int p[11];
long long dp[22][2][2];
long long poww[22];
void pre()
{
poww[0] = 1;
for ( int i = 1; i <= 18; i++ ) poww[i] = poww[i-1]*10;
return;
}
long long f(int idx, int tight, int flag)
{
if ( idx == n ) {
if ( flag ) return 1;
return 0;
}
long long &ans = dp[idx][tight][flag];
if ( ans != -1 ) return ans;
ans = 0;
if ( tight == 0 ) {
if ( flag ) {
ans = poww[n-idx];
return ans;
}
for ( int i = 0; i <= 9; i++ ) {
ans += f(idx+1, 0, flag | p[i]);
}
}
else {
for ( int i = 0; i <= s[idx]-49; i++ ) {
ans += f(idx+1, 0, flag | p[i]);
}
ans += f(idx+1, 1, flag | p[s[idx]-48]);
}
return ans;
}
int main()
{
p[2] = p[3] = p[5] = p[7] = 1;
int t;
pre();
scanf("%d", &t);
while ( t-- ) {
scanf("%s", s);
long long int i,j,k;
n = (long long int)(strlen(s));
for (i = 0; i < n; i++ ) {
for ( j = 0; j < 2; j++ ) {
for ( k = 0; k < 2; k++ ) dp[i][j][k] = -1;
}
}
long long ans = f(0,1,0);
printf("%lld\n", ans);
}
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8ZnN0cmVhbT4KI2luY2x1ZGUgPGNzdHJpbmc+CiNpbmNsdWRlIDxhbGdvcml0aG0+CiNpbmNsdWRlIDxzdHJpbmc+CiNpbmNsdWRlIDxjc3RkaW8+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CmNoYXIgc1syMl07CmxvbmcgbG9uZyBpbnQgbjsKbG9uZyBsb25nIGludCBwWzExXTsKbG9uZyBsb25nIGRwWzIyXVsyXVsyXTsKbG9uZyBsb25nIHBvd3dbMjJdOwp2b2lkIHByZSgpCnsKICAgICBwb3d3WzBdID0gMTsKICAgICBmb3IgKCBpbnQgaSA9IDE7IGkgPD0gMTg7IGkrKyApIHBvd3dbaV0gPSBwb3d3W2ktMV0qMTA7CiAgICAgcmV0dXJuOwp9CmxvbmcgbG9uZyBmKGludCBpZHgsIGludCB0aWdodCwgaW50IGZsYWcpCnsKCWlmICggaWR4ID09IG4gKSB7CgkJaWYgKCBmbGFnICkgcmV0dXJuIDE7CgkJcmV0dXJuIDA7Cgl9Cglsb25nIGxvbmcgJmFucyA9IGRwW2lkeF1bdGlnaHRdW2ZsYWddOwoJaWYgKCBhbnMgIT0gLTEgKSByZXR1cm4gYW5zOwoJYW5zID0gMDsKCWlmICggdGlnaHQgPT0gMCApIHsKICAgICAgICBpZiAoIGZsYWcgKSB7CiAgICAgICAgICAgIGFucyA9IHBvd3dbbi1pZHhdOwoJCSAgICByZXR1cm4gYW5zOwoJICAgIH0gCgkJZm9yICggaW50IGkgPSAwOyBpIDw9IDk7IGkrKyApIHsKCQkJYW5zICs9IGYoaWR4KzEsIDAsIGZsYWcgfCBwW2ldKTsKCQl9Cgl9CgllbHNlIHsKCQlmb3IgKCBpbnQgaSA9IDA7IGkgPD0gc1tpZHhdLTQ5OyBpKysgKSB7CgkJCWFucyArPSBmKGlkeCsxLCAwLCBmbGFnIHwgcFtpXSk7CgkJfQoJCWFucyArPSBmKGlkeCsxLCAxLCBmbGFnIHwgcFtzW2lkeF0tNDhdKTsKCX0KCXJldHVybiBhbnM7Cn0KaW50IG1haW4oKQp7CglwWzJdID0gcFszXSA9IHBbNV0gPSBwWzddID0gMTsKCWludCB0OwoJcHJlKCk7CglzY2FuZigiJWQiLCAmdCk7Cgl3aGlsZSAoIHQtLSApIHsKICAgICAgICBzY2FuZigiJXMiLCBzKTsgIAogICAgICAgIGxvbmcgbG9uZyBpbnQgaSxqLGs7CgkJbiA9IChsb25nIGxvbmcgaW50KShzdHJsZW4ocykpOwoJCWZvciAoaSA9IDA7IGkgPCBuOyBpKysgKSB7CiAgICAgICAgICAgIGZvciAoIGogPSAwOyBqIDwgMjsgaisrICkgewogICAgICAgICAgICAgICAgZm9yICggIGsgPSAwOyBrIDwgMjsgaysrICkgZHBbaV1bal1ba10gPSAtMTsKICAgICAgICAgICAgfQogICAgICAgIH0KCQlsb25nIGxvbmcgYW5zID0gZigwLDEsMCk7CgkJcHJpbnRmKCIlbGxkXG4iLCBhbnMpOwoJfQoJcmV0dXJuIDA7Cn0gIA==