#include<bits/stdc++.h>
using namespace std;
using ll= long long;

ll fun(string s,ll mid,ll m )
{
    ll val=0,z=1;

    for(ll i=s.size()-1; i>=0; i--)
    {
        ll t=s[i]-'0';

        if(t>(m/z))
        {
            val=m+1;
            break;
        }
        val+=t*z;
        if(val>m)
        {
            val=m+1;
            break;
        }
        if(z> (m/mid) &&i>0 )
        {
            val=m+1;
            break;
        }
        if( z>(m/mid) &&i==0 )
        {

            break;
        }
        z=z*mid;
        //  cout<<"z="<<z<<endl;
    }
    return val;
}


int main()
{

    ll m;
    string s;
    cin>>s;
    cin>>m;

    if(s.size()==1)
    {
        int t=s[0]-'0';
      //  t++;
        if(t<=m)
            cout<<1<<endl;
        else
            cout<<0<<endl;
        return 0;
    }

    ll mx=0;
    for(int i=0; i<s.size(); i++)
    {
        ll x=s[i]-'0';
        mx=max(mx,x);
    }
    ll lw=mx+1;
    ll w=mx+1;
    ll ub=m;
    ll k=0;
    while(lw<=ub)
    {
        ll mid=lw+(ub-lw)/2;
        ll v=fun(s,mid,m);

       // cout<<"v="<<v<<" mid="<<mid<<endl;
        if(v<=m)
        {
            lw=mid+1;
            k=mid;
        }
        else if(v>m)
        {
            ub=mid-1;
        }
//cout<<lw<<" "<<ub<<endl;
    }
    ll e=0;
    ll f=k-mx;
    cout<<max(e,f)<<endl;

    return 0;
}


#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>

#define space putchar(' ')
#define enter putchar('\n') 
#define MAXN 

using namespace std;

typedef long long int64;

int read() {
	int f = 1,res = 0;
	char ch = getchar();
	while(ch < '0' || ch > '9') {
		if(ch == '-') f *= -1;
		ch = getchar();
	}
	while('0' <= ch && ch <= '9') {
		res = res*10+ch-'0';
		ch = getchar();
	}
	return res*f;
}

void out(int i) {
	if(i < 0) {
		putchar('-');
		i = -i;
	}
	if(i > 9) out(i/10);
	putchar(i%10+'0');
	return;
}



int main() {
	string s;
	string t = "atcoder";
	int T = read();
	while(T--) {
		cin>>s;
		if(s > t) {
			puts("0");
			continue;
		}
		bool f = true;
		int k = 0;
		for(int i = 0; i < s.size(); i++) {
			if(s[i] != 'a') {
				f = false;
				k = i;
				break;
			}
		}
		if(f) {
			puts("-1");
			continue;
		}
		for(int i = 0; i < k; i++) {
			swap(s[k-i],s[k-i-1]);
			if(s > t) {
				out(i+1);enter;
				break;
			}
		}
	}
	
	return 0;
}