#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 10;
int pa[N][3], pb[N][3], n, p[N][3][3], c[3][3];
void init(string a, string b) {
n = a.size();
for (int i = 0; i < n; ++i) {
int ca = (a[i] == 'A' ? 0 : (a[i] == 'T' ? 1 : 2));
int cb = (b[i] == 'A' ? 0 : (b[i] == 'T' ? 1 : 2));
pa[i + 1][ca]++;
pb[i + 1][cb]++;
p[i + 1][ca][cb]++;
for (int j = 0; j < 3; ++j) {
pa[i + 1][j] += pa[i][j];
pb[i + 1][j] += pb[i][j];
for (int k = 0; k < 3; ++k) {
p[i + 1][j][k] += p[i][j][k];
}
}
}
}
int get_distance(int x, int y) {
for (int i = 0; i < 3; ++i) {
if (pa[y + 1][i] - pa[x][i] != pb[y + 1][i] - pb[x][i]) {
return -1;
}
}
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
c[i][j] = p[y + 1][i][j] - p[x][i][j];
}
}
int ans = 0;
for (int i = 0; i < 3; ++i) {
for (int j = i + 1; j < 3; ++j) {
int z = min(c[i][j], c[j][i]);
c[i][j] -= z;
c[j][i] -= z;
ans += z;
}
}
vector<int> d0, d1;
for (int i = 0; i < 3; ++i) {
d0.push_back(c[i][(i + 1) % 3]);
d1.push_back(c[i][(i + 2) % 3]);
}
sort(d0.begin(), d0.end());
sort(d1.begin(), d1.end());
assert(d0[0] == d0[2] && d1[0] == d1[2]);
assert(d0[0] == 0 || d1[0] == 0);
return 2 * (d0[0] + d1[0]) + ans;
}
// int32_t main() {
// ios::sync_with_stdio(false);
// cin.tie(nullptr);
// int m, q;
// cin >> m >> q;
// string a, b;
// for (int i = 0; i < m; ++i) {
// int c = rand() % 3;
// if (c == 0) a += 'A';
// if (c == 1) a += 'T';
// if (c == 2) a += 'C';
// }
// b = a;
// random_shuffle(b.begin(), b.end());
// init(a, b);
// cout << a << "\n";
// cout << b << "\n";
// for (int i = 0; i < m; ++i) {
// for (int j = i; j < m; ++j) {
// cout << "! " << i << ' ' << j << ' ' << get_distance(i, j) << '\n';
// }
// }
// return 0;
// }
