#include <bits/stdc++.h>

typedef long long ll;
#define llinf 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define SZ(x) (int)x.size()
#define mp make_pair
#define pii pair<int, int>
#define vi vector<int>
#define pb push_back

using namespace std;

char s[1005], t[1005];

string atc = "0atcoder";

vector<int> vec[26];

int main() {
    int T;
    scanf("%d", &T);
    atc += 'a' - 1;
    while (T--) {
        scanf("%s", s + 1);
        int n = strlen(s + 1);


        if (n == 1) {
            if (s[1] == 'a') {
                printf("-1\n");
                continue;
            } else {
                printf("0\n");
                continue;
            }
        }

        int fg = 0;
        for (int i = 1; i <= min(n, 8); i++) {
            if (s[i] < atc[i]) break;
            else if (s[i] > atc[i]) {
                fg = 1;
                break;
            }
        }

        for (int i = 0; i < 26; i++) vec[i].clear();
        for (int i = 1; i <= n; i++) vec[s[i] - 'a'].pb(i);

        if (fg) {
            printf("0\n");
            continue;
        }


        int cnt = 1;
        for (int i = 25; i >= 0; i--) {
            for (int j = 0; j < SZ(vec[i]); j++) {
                t[cnt++] = 'a' + i;
            }
        }

        fg = 1;
        for (int i = 1; i <= min(n, 8); i++) {
            if (t[i] < atc[i]) {
                fg = 0;
                break;
            } else if (t[i] > atc[i]) break;
        }

        if (!fg) {
            printf("-1\n");
            continue;
        }

        int minn = inf;
        for (int i = 1; i <= min(n, 7); i++) {
            if (s[i] < atc[i]) {
                for (int j = atc[i] - 'a' + 1; j < 26; j++) {
                    if (!SZ(vec[j])) continue;
                    int pos = upper_bound(vec[j].begin(), vec[j].end(), i) - vec[j].begin();
                    if (pos == SZ(vec[j])) continue;

                    minn = min(minn, vec[j][pos] - i);
                }
                break;
            } else if (s[i] == atc[i]) {
                for (int j = atc[i] - 'a' + 1; j < 26; j++) {
                    if (!SZ(vec[j])) continue;
                    int pos = upper_bound(vec[j].begin(), vec[j].end(), i) - vec[j].begin();
                    if (pos == SZ(vec[j])) continue;
                    // printf("%d %d %d\n", j, vec[j][pos], i);
                    minn = min(minn, vec[j][pos] - i);
                }
            }
        }
        printf("%d\n", minn);


    }
}
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9+7;
int dist[2000][2000];
bool done[26];
signed main(){
    int h,w;
    string a[2000];
    cin>>h>>w;
    pair<int,int>s,g;
    vector<pair<int,int>>pos[26];
    for(int i=0;i<h;i++){
        cin>>a[i];
        for(int j=0;j<w;j++){
            if(a[i][j]>='a'&&a[i][j]<='z')
                pos[a[i][j]-'a'].emplace_back(i,j);
            if(a[i][j]=='S')
                s=make_pair(i,j);
            if(a[i][j]=='G')
                g=make_pair(i,j);
        }
    }
    for(int i=0;i<h;i++)
        for(int j=0;j<w;j++)
            dist[i][j]=mod;
    int dx[]={1,0,0,-1},dy[]={0,1,-1,0};
    queue<pair<int,int>>que;
    que.push(s);
    dist[s.first][s.second]=0;
    while(!que.empty()){
        pair<int,int>p=que.front();
        que.pop();
        if(g==p){
            cout<<dist[g.first][g.second]<<endl;
            return 0;
        }
        if(a[p.first][p.second]>='a'&&a[p.first][p.second]<='z'&&!done[a[p.first][p.second]-'a']){
            done[a[p.first][p.second]-'a']=1;
            for(int i=0;i<pos[a[p.first][p.second]-'a'].size();i++){
                pair<int,int>np=pos[a[p.first][p.second]-'a'][i];
                if(dist[np.first][np.second]==mod){
                    dist[np.first][np.second]=dist[p.first][p.second]+1;
                    que.push(np);
                }
            }
        }
        for(int i=0;i<4;i++){
            pair<int,int>np=make_pair(p.first+dx[i],p.second+dy[i]);
            if(np.first<0||np.first>=h||np.second<0||np.second>=w)
                continue;
            if(a[p.first][p.second]>='a'&&a[p.first][p.second]<='z'&&a[p.first][p.second]==a[np.first][np.second])
                continue;
            if(a[np.first][np.second]=='#')
                continue;
            if(dist[np.first][np.second]==mod){
                dist[np.first][np.second]=dist[p.first][p.second]+1;
                que.push(np);
            }
        }
    }
    cout<<-1<<endl;
    return 0;
}