#include<iostream>
#include<unordered_map>
 
using namespace std;
using ll = long long;
 
 
int solve(ll N){
  unordered_map<ll, int> memo;
  auto f = [&](auto self, ll N) -> int {//这一行。
    if(N==0) return 0;
    if(memo.count(N)) return memo[N];
    
    ll n = N / 10, r = N % 10;
    int res = 0;
    if(1 <= r && r <= 3 && self(self, n) <= 1) res = 1;
    else if(2 <= r && r <= 6 && self(self, n) <= 2) res = 2;
    else if(3 <= r && r <= 9 && self(self, n) <= 3) res = 3;
    else if(4 <= r && r <= 9 && self(self, n) <= 4) res = 4;
    else if(0 <= r && r <= 2 && self(self, n - 1) <= 4) res = 4;
    else res = 5;
    memo[N] = res;
    return res;
  };
  return f(f, N);
}
 
int main(){
  int T; cin >> T;
  for(int t=0; t<T; ++t){
    ll N; cin >> N;
    cout << solve(N) << endl;
  }
}