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

const int P = 998244353;
//const int P = 1e9 + 7;
//const int P = 1e9 + 9;
int mul(const int &x, const int &y) { return 1ll * x * y % P; }
int qpow(int x, int y) {
	if (y < 0) {
		y += P - 1;
	}
	int r = 1;
	while (y) {
		if (y & 1) {
			r = mul(r, x);
		}
		x = mul(x, x);
		y /= 2;
	}
	return r;
}
int inc(const int &x, const int &y) {
	if (x + y >= P) {
		return x + y - P;
	} else {
		return x + y;
	}
}
int sub(const int &x, const int &y) {
	if (x < y) {
		return x - y + P;
	} else {
		return x - y;
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int t;
	cin >> t;
	while (t--) {
		std::string s;
		cin >> s;
		int n = (int)s.size();
		std::string t = "atcoder";
		if (s > t) {
			cout << 0 << '\n';
			continue;
		}
		bool flag = true;
		for (int i = 0; i < n; i++) {
			if (s[i] != 'a') {
				flag = false;
			}
		}
		if (flag) {
			cout << -1 << '\n';
			continue;
		}
		int ans = n + 1;
		for (int i = 0; i < n; i++) {
			int cnt = 0;
			std::string temp = s;
			for (int j = i; j >= 1; j--) {
				swap(temp[j], temp[j - 1]);
				++cnt;
				if (cnt >= ans) {
					break;
				}
				if (temp > t) {
					ans = cnt;
					break;
				}
			}
			cnt = 0;
			temp = s;
			for (int j = i; j < n - 1; j++) {
				swap(temp[j], temp[j + 1]);
				++cnt;
				if (cnt >= ans) {
					break;
				}
				if (temp > t) {
					ans = cnt;
					break;
				}
			}
		}
		cout << ans << '\n';
	}
	return 0;
}
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
#pragma region DEBUG
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef
tree<
  pair<int,int>,
  null_type,
  less<pair<int,int>>,
  rb_tree_tag,
  tree_order_statistics_node_update>
ordered_set;
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
#pragma endregion DEBUG
#define MOD 1000000007
#define MAX 500005
#define endl "\n"
vector <lli> fact(MAX,1);
vector <lli> invfact(MAX,1);
lli n;
vector <lli> arr;
lli dp[3005][3005];
map <lli, vector<vector<lli> >> adj;
vector <lli> pre;
lli ctr = 0;
lli f(lli idx, lli head){
    if(head > n)
        return 0;
    if(idx == n+1)
        return 1;
   // debug("Yeet");
   
    if(dp[idx][head] != -1)
        return dp[idx][head];
    lli ans = 0;
    lli sum = 0;
    lli prefsum = pre[idx-1]%head;
    for(auto i : adj[head][prefsum]){
        if(i >= idx){
            if(i+1 == n+1){
                ans += 1;
            }
            else{
                ans += f(i+1,head+1);
                ans += f(i+1,head);
            }
            break;
        }
    }   
    ans %= MOD;
    //debug(idx,head,ans);
    //debug(ans);
    return dp[idx][head] = ans;
}
void solve(){
    cin>>n;
    arr.resize(n);
    pre.resize(n+1,0);
    for(lli i = 0; i<=n+1; i++){
        for(lli j = 0; j<=n+1; j++){
            dp[i][j] = -1;
        }
    }
    for(lli i = 0; i<n; i++){
        cin>>arr[i];
        pre[i+1] = pre[i] + arr[i];
    }
    for(lli head = 1; head <=n; head++){
        adj[head].resize(head);
        lli sum = 0;
        adj[head][0].push_back(0);
        for(lli i = 0; i<n; i++){
            sum += arr[i];
            sum %= head;
            adj[head][sum].push_back(i+1);
        }
    }
  //  debug("Yoot");
    //debug(adj[1]);
    lli valx = f(1,1);
    cout<<valx<<endl;
}
int main(){
    /* freopen("input.txt", "r", stdin); 
    freopen("output1.txt", "w", stdout); */
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
   /*  for(lli i = 1; i<MAX-5; i++){
        fact[i] = i*fact[i-1]%MOD;
        invfact[i] = binpow(fact[i],MOD-2);
    } */
    lli t;
    t = 1;
    //cin>>t;
    lli p = 0;
    while(t--){
        p++;
        solve();
    }
}