//反向62

 #include <iostream>

 #include <algorithm>

 #include <string>

 #include <cstring>

 #include <cstdio>

 using namespace std;

 typedef long long ll;

 // const int maxn = 1e5+5;

 ll n;

 ll a[];

 ll dp[][];

 //下标，前面是否4，是否有前导0， 是否有限制

 ll dfs(ll pos, ll sta, ll pre, ll limit){

     if(pos == -) return ;

     if(!limit && dp[pos][sta] != -)

         return dp[pos][sta];

     int up = limit?a[pos]:;

     ll ans = ;

     for(int i = ;i <= up;i++){

         if(pre ==  && i == ){

             continue;

         }

         ans += dfs(pos-, i == , i, limit && i == a[pos]);

     }

     if(!limit) dp[pos][sta] = ans;

     return ans;

 }

 ll solve(ll x){

     ll pos = ;

     while(x){

         a[pos++] = x%;

         x /= ;

     }

     return dfs(pos-, , -, true);

 }

 int main(){

     memset(dp, -, sizeof dp);

     int t;

     scanf("%d", &t);

     while(t--){

         scanf("%lld", &n);

         ll ans = solve(n);

         printf("%lld\n", n - ans + );

     }

     return ;

 }