#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define db double
#define ll __int128
#define pb push_back
#define fs first
#define sd second
#define Mod long(1e9 + 7)
#define all(x) x.begin(), x.end()
#define unvisited long(-1)
#define Eps double(1e-9)
#define _for(i, n) for(int i = 0; i < (n); i++)
#define dbg(x) cout << #x ": " << x << endl;
const int Max = 5e3 + 7, Inf = 2e8 + 7;
void print(bool x) { cout << (x ? "YES" : "NO") << endl; }
string tostring (__int128 x)
{
string ans = "";
while(x > 0)
{
ans += (x % 10 + '0');
x /= 10;
}
reverse(all(ans));
return ans;
}
vector <vector <int>> s;
vector <vector <vector<int>>> f;
void init(string a, string b)
{
int n = (int) a.size(); string ref = "ATC";
map <char, int> mp;
for(int i = 0; i < (int) ref.size(); i++)
mp[ref[i]] = i;
s.assign(n + 1, vector <int> ((int) ref.size() + 1, 0));
for(int i = 0; i < n; i++)
{
s[i][mp[a[i]]]++; s[i][mp[b[i]]]--;
for(int j = 0; j < (int) ref.size(); j++)
s[i][j] += (i > 0 ? s[i-1][j] : 0);
}
f.assign(n + 1, vector <vector<int>> (3, vector <int> (3, 0)));
for(int i = 0; i < n; i++)
{
int _a = mp[a[i]], _b = mp[b[i]];
f[i][_a][_b]++;
for(int j = 0; j < 3; j++) if(i > 0)
for(int k = 0; k < 3; k++)
f[i][j][k] += f[i-1][j][k];
}
}
int get_distance(int x, int y)
{
bool can = true;
for(int i = 0; i < 3; i++)
{
int t = s[y][i];
if(x != 0) t -= s[x-1][i];
if(t != 0) can = false;
}
int ans = 0, cont = 0;
for(int i = 0; i < 3; i++)
{
for(int j = i + 1; j < 3; j++)
{
int t1 = 0, t2 = 0;
if(x > 0)
{
t1 = f[x-1][i][j];
t2 = f[x-1][j][i];
}
ans += min(f[y][i][j] - t1, f[y][j][i] - t2);
cont += abs((f[y][i][j] - t1) - (f[y][j][i] - t2));
}
}
cont /= 3; ans += cont * 2;
return (can ? ans : -1);
}
