t = int(input())
for _ in range(t):
    k, s = input(), input()
    res = 0
    for i in range(1, len(s)):
        res += abs(k.index(s[i]) - k.index(s[i - 1]))
    print(res)

t = int(input())
maps = [
    lambda x: 0,
    lambda x: x,
    lambda x: -1,
    lambda x: -x - 1
]

for _ in range(t):
    x0, n = map(int, input().split())
    d = maps[n % 4](n)
    print(x0 - d if x0 % 2 == 0 else x0 + d)

t = int(input())

for _ in range(t):
    n = int(input())
    a = sorted(list(map(int, input().split())))
    res = a[0]
    for i in range(n - 1):
        res = max(res, a[i + 1] - a[i])
    print(res)

#include <bits/stdc++.h>

using namespace std;

#define forn(i, n) for (int i = 0; i < int(n); i++)

int main() {
    int t;
    cin >> t;
    forn(tt, t) {
        int n;
        cin >> n;
        vector<int> a(n);
        forn(i, n)
            cin >> a[i];

        string c;
        cin >> c;

        vector<int> l, r;
        forn(i, n)
            (c[i] == 'B' ? l : r).push_back(a[i]);
        sort(l.begin(), l.end());
        sort(r.begin(), r.end(), greater<int>());

        bool ok = true;
        forn(i, l.size())
            if (l[i] < i + 1)
                ok = false;
        forn(i, r.size())
            if (r[i] > n - i)
                ok = false;

        cout << (ok ? "YES" : "NO") << '\n';
    }
}

#include <bits/stdc++.h>

using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;
        string s;
        cin >> s;

        int bx = 0, by = 0;
        int min_bx = 0, max_bx = 0, min_by = 0, max_by = 0;
        for (char c: s) {
            if      (c == 'L') min_by = min(min_by, --by);
            else if (c == 'R') max_by = max(max_by, ++by);
            else if (c == 'U') min_bx = min(min_bx, --bx);
            else               max_bx = max(max_bx, ++bx);

            if (max_bx - min_bx >= n) {
                if (bx == min_bx) min_bx++;
                break;
            }
            if (max_by - min_by >= m) {
                if (by == min_by) min_by++;
                break;
            }
        }

        cout << 1 - min_bx << ' ' << 1 - min_by << '\n';
    }
}

#include <bits/stdc++.h>

using namespace std;

typedef vector<int> vi;
typedef pair<int, int> pii;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;
        vector<string> dir(n);
        for (int i = 0; i < n; i++)
            cin >> dir[i];

        vector<vi> res(n, vi(m, 0));
        int opt = 0, optr = 0, optc = 0;
        for (int r = 0; r < n; r++) {
            for (int c = 0; c < m; c++) {
                if (res[r][c] > 0)
                    continue;

                int nr = r, nc = c;
                int depth = 0;
                vector<pii> path;
                auto ok = [&n, &m](int row, int col) {
                    return row > -1 && row < n && col > -1 && col < m;
                };

                do {
                    res[nr][nc] = --depth;
                    path.emplace_back(nr, nc);
                    if (dir[nr][nc] == 'L')
                        nc--;
                    else if (dir[nr][nc] == 'R')
                        nc++;
                    else if (dir[nr][nc] == 'U')
                        nr--;
                    else
                        nr++;
                } while (ok(nr, nc) && res[nr][nc] == 0);

                int start = 1;
                if (ok(nr, nc)) {
                    if (res[nr][nc] < 0) {
                        int cycle = res[nr][nc] - depth + 1;
                        for (int i = 0; i < cycle; i++) {
                            auto p = path.back();
                            path.pop_back();
                            res[p.first][p.second] = cycle;
                        }
                    }
                    start = res[nr][nc] + 1;
                }
                while (!path.empty()) {
                    auto p = path.back();
                    path.pop_back();
                    res[p.first][p.second] = start++;
                }

                if (res[r][c] > opt) {
                    opt = res[r][c];
                    optr = r;
                    optc = c;
                }
            }
        }

        cout << optr + 1 << ' ' << optc + 1 << ' ' << opt << '\n';
    }
}

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;
        vector<pii> dishes(n);
        ll balance = 0;
        ll max_a = 0, max_b = 0;
        ll total_eat = static_cast<long long>(n) * m;

        for (int i = 0; i < n; i++) {
            cin >> dishes[i].first >> dishes[i].second;
            balance += dishes[i].first - dishes[i].second;
            max_a += min(m, dishes[i].first);
            max_b += min(m, dishes[i].second);
        }
        ll max_delta = 2 * max_a - total_eat, min_delta = total_eat - 2 * max_b;
        ll min_a = total_eat - max_b;

        ll eat_a;
        if (balance < 0) {
            eat_a = min_a;
            if (balance - min_delta >= 0)
                eat_a = min(max_a, (total_eat + balance + 1) / 2);
        } else {
            eat_a = max_a;
            if (balance - max_delta <= 0)
                eat_a = min(max_a, (total_eat + balance + 1) / 2);
        }
        ll ans = abs(balance - 2 * eat_a + total_eat);

        cout << ans << '\n';
        ll rest_a = eat_a - min_a;
        for (int i = 0; i < n; i++) {
            ll cur_a = 0;
            if (dishes[i].second < m)
                cur_a += m - dishes[i].second;
            ll add = min(rest_a, min(m - cur_a, dishes[i].first - cur_a));
            cur_a += add;
            rest_a -= add;
            cout << cur_a << ' ' << m - cur_a << '\n';
        }
    }
}

#include <bits/stdc++.h>

using namespace std;

#define forn(i, n) for (int i = 0; i < int(n); i++)

struct seg {
    int a, b, m;
    int index;
};

int n, ans;
vector<seg> segments;
map<int, vector<seg>> diags;

void erase(multiset<pair<pair<int,int>, int>>& lr, int l, int r, int index) {
    pair<pair<int,int>,int> plr = make_pair(make_pair(l, r), index);
    auto i = lr.find(plr);
    assert(i != lr.end());
    lr.erase(i);
}

void erase(multiset<pair<pair<int,int>, int>>& lr, multiset<pair<pair<int,int>, int>>& rl, int l, int r, int index) {
    erase(lr, l, r, index);
    erase(rl, r, l, index);
}

map<int, pair<int,int>> dd;

void setup_dd(int index, int value) {
    assert(dd.count(index) == 0);
    int x = segments[index].a - value;
    int y = segments[index].m - x;
    assert(segments[index].a - x >= 0);
    assert(segments[index].b - y >= 0);
    assert(x + y == segments[index].m);
    dd[index] = make_pair(x, y);
}

int solve(vector<seg> s) {
    int n = s.size();
    multiset<pair<pair<int,int>, int>> lr;
    multiset<pair<pair<int,int>, int>> rl;
    forn(i, n) {
        int min_d = max(s[i].m - s[i].b, 0);
        int max_d = min(s[i].a, s[i].m);
        lr.insert(make_pair(make_pair(s[i].a - max_d, s[i].a - min_d), s[i].index));
        rl.insert(make_pair(make_pair(s[i].a - min_d, s[i].a - max_d), s[i].index));
    }

    int result = 0;
    while (!rl.empty()) {
        result++;
        auto min_r_iterator = rl.begin();
        int r = min_r_iterator->first.first;
        int l = min_r_iterator->first.second;
        int index = min_r_iterator->second;
        erase(lr, rl, l, r, index);
        setup_dd(index, r);

        while (!lr.empty()) {
            auto min_l_iterator = lr.begin();
            int ll = min_l_iterator->first.first;
            int rr = min_l_iterator->first.second;
            int ii = min_l_iterator->second;
            if (ll <= r) {
                erase(lr, rl, ll, rr, ii);
                setup_dd(ii, r);
            } else
                break;
        }
    }

    return result;
}

int main() {
    int t;
    cin >> t;
    forn(tt, t) {
        cin >> n;
        diags.clear();
        dd.clear();
        segments = vector<seg>(n);
        forn(i, n) {
            seg s;
            s.index = i;
            cin >> s.a >> s.b >> s.m;
            diags[s.a + s.b - s.m].push_back(s);
            segments[i] = s;
        }
        int sum = 0;
        for (auto p: diags)
            sum += solve(p.second);
        cout << sum << '\n';
        forn(i, n)
            cout << dd[i].first << " " << dd[i].second << '\n';
    }
}

#include <bits/stdc++.h>

using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        string s;
        cin >> s;
        cout << (count(s.begin(), s.end(), 'B') * 2 == s.size() ?
                 "YES\n" : "NO\n");
    }
}

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n);
        vector<pii> actions;
        for (int i = 0; i < n; i++)
            cin >> a[i];

        for (int i = 0; i < n - 1; i++) {
            int min_pos = i;
            for (int j = i + 1; j < n; j++)
                if (a[j] < a[min_pos])
                    min_pos = j;

            if (min_pos > i) {
                actions.push_back({i, min_pos});
                int opt = a[min_pos];
                for (int j = min_pos; j > i; j--)
                    a[j] = a[j - 1];
                a[i] = opt;
            }
        }

        cout << actions.size() << '\n';
        for (auto &lr: actions) {
            cout << lr.first + 1 << ' ' << lr.second + 1 << ' ' << lr.second - lr.first << '\n';
        }
    }

}

#include <bits/stdc++.h>

using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, m, k;
        cin >> n >> m >> k;
        vector<vector<int>> status(n, vector<int>(m, 0));
        for (int i = 0; i < n; i++) {
            string s;
            cin >> s;
            for (int j = 0; j < m; j++)
                if (s[j] == '*')
                    status[i][j] = 1;
        }
        for (int i = n - 1; i > -1; i--) {
            for (int j = 0; j < m; j++) {
                if (status[i][j] == 0)
                    continue;
                int len = 0;
                while (j > len && j + len + 1 < m && i > len) {
                    if (status[i - len - 1][j - len - 1] == 0 || status[i - len - 1][j + len + 1] == 0)
                        break;
                    len++;
                }
                if (len >= k) {
                    for (int d = 0; d <= len; d++) {
                        status[i - d][j - d] = 2;
                        status[i - d][j + d] = 2;
                    }
                }
            }
        }
        bool ok = true;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (status[i][j] == 1)
                    ok = false;

        cout << (ok ? "YES" : "NO") << '\n';
    }
}

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        auto cmp = [](pii const &x, pii const &y) {
            return x > y;
        };
        set<pii, decltype(cmp)> a(cmp);
        vector<pii> answer;
        for (int i = 0; i < n; i++) {
            int ai;
            cin >> ai;
            if (ai > 0)
                a.emplace(ai, i + 1);
        }
        while (a.size() > 1) {
            auto p1 = *a.begin();
            a.erase(a.begin());
            auto p2 = *a.begin();
            a.erase(a.begin());
            answer.emplace_back(p1.second, p2.second);
            if (p1.first > 1) a.emplace(p1.first - 1, p1.second);
            if (p2.first > 1) a.emplace(p2.first - 1, p2.second);
        }
        cout << answer.size() << '\n';
        for (auto &p : answer) {
            cout << p.first << ' ' << p.second << '\n';
        }
    }
}

#include <bits/stdc++.h>

using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, a;
        cin >> n;
        deque<int> d;
        for (int i = 0; i < n; i++) {
            cin >> a;
            if (d.empty() || a < d[0])
                d.push_front(a);
            else
                d.push_back(a);
        }
        for (int x : d)
            cout << x << ' ';
        cout << '\n';
    }
}

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef pair<int, int> node;
typedef tree<node, null_type, less<node>,
            rb_tree_tag, tree_order_statistics_node_update> ordered_set;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        ordered_set s;
        long long cnt = 0;
        for (int i = 0; i < n; i++) {
            int a;
            cin >> a;
            int less = s.order_of_key(node(a, 0)),
                    greater = i - s.order_of_key(node(a, n));
            cnt += min(less, greater);
            s.insert(node(a, i));
        }
        cout << cnt << '\n';
    }
}

#include <bits/stdc++.h>

using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, d;
        cin >> n >> d;
        vector<int> a(n);
        for (int i = 0; i < n; i++)
            cin >> a[i];
        vector<bool> used(n, false);
        bool fail = false;
        int res = 0;
        for (int i = 0; i < n; i++) {
            if (used[i])
                continue;
            int cur = i, pref = 0, last = 0, iter = 0, ans = 0;
            do {
                used[cur] = true;
                if (a[cur] == 0) {
                    ans = max(ans, last);
                    last = 0;
                } else {
                    last++;
                    if (iter == pref) {
                        pref++;
                    }
                }
                cur = (cur + d) % n;
                iter++;
            } while (cur != i);
            if (iter != pref)
                ans = max(ans, pref + last);
            else {
                fail = true;
                break;
            }
            res = max(res, ans);
        }
        if (fail)
            cout << "-1\n";
        else
            cout << res << '\n';
    }
}

#include <bits/stdc++.h>

using namespace std;

const int INF = 1000000000;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n);
        int maxl = 0;
        for (int i = 0; i < n; i++) {
            cin >> a[i];
            maxl = max(maxl, a[i]);
        }
        vector<vector<int>> dp(n + 1, vector<int>(2 * maxl + 1, INF));
        dp[0][0] = 0;
        for (int i = 0; i < n; i++) {
            for (int left = 0; left <= 2 * maxl; left++) {
                if (dp[i][left] == INF)
                    continue;
                dp[i + 1][max(left - a[i], 0)] = min(dp[i + 1][max(left - a[i], 0)], dp[i][left] + a[i]);
                if (left + a[i] < dp[i + 1].size()) {
                    dp[i + 1][left + a[i]] = min(dp[i + 1][left + a[i]], max(dp[i][left] - a[i], 0));
                }
            }
        }

        int ans = 2 * maxl + 1;
        for (int left = 0; left <= 2 * maxl; left++)
            ans = min(ans, left + dp[n][left]);
        cout << ans << '\n';
    }
}

#include <bits/stdc++.h>

using namespace std;

#define forn(i, n) for (int i = 0; i < int(n); i++)

int main() {
    int t;
    cin >> t;
    forn(tt, t) {
        vector<int> a(2), b(2), f(2);
        cin >> a[0] >> a[1];
        cin >> b[0] >> b[1];
        cin >> f[0] >> f[1];
        int ans = abs(a[0] - b[0]) + abs(a[1] - b[1]);
        if ((a[0] == b[0] && a[0] == f[0] && min(a[1], b[1]) < f[1] && f[1] < max(a[1], b[1]))
                || (a[1] == b[1] && a[1] == f[1] && min(a[0], b[0]) < f[0] && f[0] < max(a[0], b[0])))
            ans += 2;
        cout << ans << endl;
    }
}

#include <bits/stdc++.h>

using namespace std;

#define forn(i, n) for (int i = 0; i < int(n); i++)

int main() {
    int t;
    cin >> t;
    forn(tt, t) {
        string s;
        cin >> s;
        size_t L = s.find('a');
        if (L == string::npos) {
            cout << "NO" << endl;
            continue;
        }
        size_t n = s.length(), R = L;
        bool yes = true;
        for (size_t i = 1; i < n; i++) {
            size_t pos = s.find(char('a' + i));
            if (pos == string::npos || (pos != L - 1 && pos != R + 1)) {
                yes = false;
                break;
            } else {
                L = min(L, pos);
                R = max(R, pos);
            }
        }
        cout << (yes ? "YES" : "NO") << endl;
    }
}

#include <iostream>
#include <vector>

typedef std::vector<int> vi;

int main() {
    int t;
    std::cin >> t;
    while (t--) {
        int k, n, m;
        std::cin >> k >> n >> m;

        vi a(n), b(m);
        for (int i = 0; i < n; i++)
            std::cin >> a[i];
        for (int i = 0; i < m; i++)
            std::cin >> b[i];

        int pos1 = 0, pos2 = 0;
        vi res;
        bool ok = true;
        while (pos1 != n || pos2 != m) {
            if (pos1 != n && a[pos1] == 0) {
                res.push_back(0);
                k++;
                pos1++;
            } else if (pos2 != m && b[pos2] == 0) {
                res.push_back(0);
                k++;
                pos2++;
            } else if (pos1 != n && a[pos1] <= k) {
                res.push_back(a[pos1++]);
            } else if (pos2 != m && b[pos2] <= k) {
                res.push_back(b[pos2++]);
            } else {
                std::cout << -1 << '\n';
                ok = false;
                break;
            }
        }

        if (ok) {
            for (int cur : res)
                std::cout << cur << ' ';
            std::cout << std::endl;
        }
    }

    return 0;
}

def f(x, y):
    return x & ~y

t = int(input())
for tt in range(t):
    n = int(input())
    a = list(map(int, input().split()))

    ans = [0] * n
    for i in range(1, n):
        ans[i] = f(ans[i - 1] ^ a[i - 1], a[i])
    print(" ".join(map(str, ans)))

#include <bits/stdc++.h>

using namespace std;

#define forn(i, n) for (int i = 0; i < int(n); i++)

int main() {
    int t;
    cin >> t;
    forn(tt, t) {
        int n, k;
        cin >> n >> k;
        vector<int> a(k);
        forn(i, k)
            cin >> a[i];
        vector<int> t(k);
        forn(i, k)
            cin >> t[i];
        vector<long long> c(n, INT_MAX);
        forn(i, k)
            c[a[i] - 1] = t[i];

        long long p;

        vector<long long> L(n, INT_MAX);
        p = INT_MAX;
        forn(i, n) {
            p = min(p + 1, c[i]);
            L[i] = p;
        }

        vector<long long> R(n, INT_MAX);
        p = INT_MAX;
        for (int i = n - 1; i >= 0; i--) {
            p = min(p + 1, c[i]);
            R[i] = p;
        }

        forn(i, n)  
            cout << min(L[i], R[i]) << " ";
        cout << endl;
    }
}

#include <iostream>
#include <vector>
#include <set>

using namespace std;

const unsigned int MAX_A = 1'000'000;
vector<unsigned int> sieve(MAX_A + 1);
vector<unsigned int> prime;

unsigned int gcd(unsigned int a, unsigned int b) {
    return b == 0 ? a : gcd(b, a % b);
}

unsigned int solve() {

    unsigned int n;
    cin >> n;
    vector<unsigned int> a(n);
    for (unsigned int i = 0; i < n; i++) {
        cin >> a[i];
    }

    unsigned int common = a[0];
    vector<set<unsigned int>> facts(n);
    for (unsigned int i = 1; i < n; i++) {
        common = gcd(common, a[i]);
    }
    for (unsigned int i = 0; i < n; i++) {
        unsigned int t = a[i] / common;
        while (t != 1) {
            facts[i].insert(sieve[t]);
            t /= sieve[t];
        }
    }

    unsigned int answer = 0;
    for (unsigned int i = 0; i < n; i++) {
        for (unsigned int p : facts[i]) {
            int l = (i + n - 1) % n, r = i;
            unsigned int cnt = 0;
            while (facts[l].count(p) > 0) {
                facts[l].erase(p);
                l--; cnt++;
                if (l < 0) {
                    l = n - 1;
                }
            }
            while (facts[r].count(p) > 0) {
                if (r != i) {
                    facts[r].erase(p);
                }
                ++r %= n; cnt++;
            }
            answer = max(answer, cnt);
        }
        facts[i].clear();
    }

    return answer;

}

int main() {

    sieve[1] = 1;
    for (unsigned int i = 2; i <= MAX_A; i++) {
        if (sieve[i] == 0) {
            sieve[i] = i;
            prime.push_back(i);
        }
        for (unsigned int j = 0; j < prime.size() && prime[j] <= sieve[i] && i * prime[j] <= MAX_A; j++) {
            sieve[i * prime[j]] = prime[j];
        }
    }

    unsigned int t;
    cin >> t;
    for (unsigned int i = 0; i < t; i++) {
        cout << solve() << '\n';
    }

}

#include <bits/stdc++.h>

using namespace std;

#define forn(i, n) for (int i = 0; i < int(n); i++)

int n;
vector<vector<int>> g;
set<int> s[2];

void dfs(int u, vector<int>& color, bool use_s) {
    color[u] = 1;
    for (int v: g[u])
        if (color[v] == 0)
            dfs(v, color, use_s);
        else if (use_s)
            s[color[v] - 1].insert(v);
    color[u] = 2;
}

int main() {
    int t;
    cin >> t;
    forn(tt, t) {
        int m;
        cin >> n >> m;
        g = vector<vector<int>>(n);
        forn(i, 2)
            s[i] = set<int>();
        forn(i, m) {
            int x, y;
            cin >> x >> y;
            x--, y--;
            g[x].push_back(y);
        }
        vector<int> color = vector<int>(n);
        dfs(0, color, true);
        vector<vector<int>> c(2, vector<int>(n));
        forn(i, 2)
            for (auto u: s[i])
                dfs(u, c[i], false);
        forn(i, n) {
            int ans = 0;
            if (color[i] != 0) {
                ans = 1;
                if (c[0][i])
                    ans = -1;
                else if (c[1][i])
                    ans = 2;
            }
            cout << ans << " ";
        }
        cout << endl;
    }
}