for _ in range(int(input())):
    s = input()
    for c in "abcdefgh":
        if c != s[0]:
            print(c + s[1], end=' ')
    for c in "12345678":
        if c != s[1]:
            print(s[0] + c, end=' ')
    print()

for _ in range(int(input())):
    s = list(input())
    n = len(s)
    upper = []
    lower = []
    for i in range(n):
        if s[i] == 'b':
            s[i] = ''
            if lower:
                s[lower.pop()] = ''
            continue
        if s[i] == 'B':
            s[i] = ''
            if upper:
                s[upper.pop()] = ''
            continue
        if 'a' <= s[i] <= 'z':
            lower += [i]
        else:
            upper += [i]
    print(''.join(s))

orda = ord('a')

def solve():
    n = int(input())
    cnt = [0] * 26
    for c in input():
        cnt[ord(c) - orda] += 1
    mx = max(cnt)
    print(max(n % 2, 2 * mx - n))


for _ in range(int(input())):
    solve()

def solve():
    n = int(input())
    seg = [list(map(int, input().split())) for x in range(n)]

    def check(k):
        ll, rr = 0, 0
        for e in seg:
            ll = max(ll - k, e[0])
            rr = min(rr + k, e[1])
            if ll > rr:
                return False
        return True

    l, r = -1, 10 ** 9
    while r - l > 1:
        mid = (r + l) // 2
        if check(mid):
            r = mid
        else:
            l = mid
    print(r)


for _ in range(int(input())):
    solve()

t = int(input())
for _ in range(t):
    n = int(input())
    cnt = 1
    while n > 0:
        d = n % 10
        n //= 10
        mul = 0
        for i in range(d + 1):
            for j in range(d + 1):
                if d - i - j >= 0:
                    mul += 1
        cnt *= mul
    print(cnt)

t = int(input())
for _ in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    a = list(reversed(a))*2
    p = [0]
    q = [0]
    for i in range(n*2-1):
        p.append(p[-1]+1 if a[i]>=a[i+1] else 0)
        q.append(q[-1]+1 if a[i]<=a[i+1] else 0)
    minn = 1000000
    for i in range(n-1,len(p)):
        if p[i] == n-1:
            minn = min(minn, i-n+1, len(p)-i+1)
        if q[i] == n-1:
            minn = min(minn, len(p)-i, i-n+2)
    print(-1 if minn == 1000000 else minn)

#include <bits/stdc++.h>

#define long long long int
#define DEBUG
using namespace std;

// @author: pashka

void solve(){
    int n;
    cin >> n;
    vector<bool> s(n);
    {
        string ss;
        cin >> ss;
        for (int i = 0; i < n; i++) {
            s[i] = ss[i] == '1';
        }
    }
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        a[i]--;
    }

    vector<int> res;
    vector<int> d(n);
    for (int i = 0; i < n; i++) {
        d[a[i]]++;
    }
    vector<int> z;
    for (int i = 0; i < n; i++) {
        if (d[i] == 0) z.push_back(i);
    }

    for (int i = 0; i < (int)z.size(); i++) {
        int x = z[i];
        int y = a[x];
        if (s[x]) {
            res.push_back(x);
            s[x] = !s[x];
            s[y] = !s[y];
        }
        d[y]--;
        if (d[y] == 0) {
            z.push_back(y);
        }
    }

    vector<bool> u(n);
    for (int i = 0; i < n; i++) {
        if (s[i] && !u[i]) {
            int x = i;
            vector<int> p;
            vector<bool> ps;
            int c = 0;
            while (!u[x]) {
                p.push_back(x);
                ps.push_back(s[x]);
                c += s[x];
                u[x] = true;
                x = a[x];
            }
            int k = p.size();
            p.push_back(x);
            ps.push_back(s[x]);
            if (c % 2 == 1) {
                cout << -1;
                return;
            }
            vector<int> v1;
            vector<bool> ps1 = ps;
            for (int j = 0; j < k; j++) {
                if (j == 0 || ps1[j]) {
                    v1.push_back(p[j]);
                    ps1[j] = !ps1[j];
                    ps1[j + 1] = !ps1[j + 1];
                }
            }
            vector<int> v2;
            vector<bool> ps2 = ps;
            for (int j = 0; j < k; j++) {
                if (j != 0 && ps2[j]) {
                    v2.push_back(p[j]);
                    ps2[j] = !ps2[j];
                    ps2[j + 1] = !ps2[j + 1];
                }
            }
            if (v1.size() < v2.size()) {
                for (auto x : v1) {
                    res.push_back(x);
                }
            } else {
                for (auto x : v2) {
                    res.push_back(x);
                }
            }
        }
    }
    cout << res.size() << "\n";
    for (auto x : res) cout << x + 1 << " ";
}

int main() {
    int t;
    cin >> t;
    for(int _ = 0; _ < t; ++_){
        solve();
        cout << "\n";
    }
    return 0;
}