很 naive 的一个想法是双向 BFS，但是 $n$ 太大不管用。

$S$ 与 $T$ 的异或值和操作一相关； $T$ 的值相同区间和操作二三相关。

11100101 11110000 00010101

对于 $T$ 的值相同区间且 $S$ 在此区间未成为目标，是否一定需要对此区间进行操作二三？

否：当有一个更大的区间可以进行操作一使得至少两个值相同区间得到满足。而操作一是由异或值决定的。

什么情况下，对一个区间只进行进行操作一比二三劣？异或值的 1 区间数量大于有值不同的值相同区间数。

有没有可能在同一个区间中操作一和二三混合使用？这种情况可能是，对于异或值 1 区间的间隙可以通过操作二三填成 1，显然不会更优。

直接 DP 单调队列解决。

混合使用处有问题：可以在一个大区间内使用操作一，再在小区间内使用操作二三。实际上不管先操作一还是二三总能实现在最小步骤实现。那么可以在状态记录使用的推平操作，然后统计答案是记录反转微调的步骤。

设 $f_{i,j}$ 表示前 $i$ 个最后一次推平或不动，然后反转微调的答案。 $\mathcal{O}(n)$ 。

这样设状态关键在于，平推和反转先后无影响，而且两种操作可以“黏住”。

const int N = 5e5 + 5;

inline ll read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

namespace Main {
	int f[2][3];
	char s[N], t[N];
	int main () {
		for (int T = read(); T--; ) {
			scanf ("%s", s + 1);
			scanf ("%s", t + 1);
			memset (f, 60, sizeof f);
			f[1][0] = (s[1] != t[1]);
			f[1][1] = (t[1] == '1') + 1;
			f[1][2] = (t[1] == '0') + 1;
			int n = strlen(s + 1);
			for (int i = 2; i <= n; i++) {
				int cur = i & 1;
				f[cur][0] = (s[i] == t[i])? min({f[cur ^ 1][0], f[cur ^ 1][1], f[cur ^ 1][2]}): min({f[cur ^ 1][0] + (s[i - 1] == t[i - 1]), f[cur ^ 1][1] + (t[i - 1] == '0'), f[cur ^ 1][2] + (t[i - 1] == '1')});
				f[cur][1] = (t[i] == '0')? min({f[cur ^ 1][1], f[cur ^ 1][0] + 1, f[cur ^ 1][2] + 1}): min({f[cur ^ 1][1] + (t[i - 1] == '0'), f[cur ^ 1][2] + (t[i - 1] == '1') + 1, f[cur ^ 1][0] + (s[i - 1] == t[i - 1]) + 1});
				f[cur][2] = (t[i] == '1')? min({f[cur ^ 1][2], f[cur ^ 1][0] + 1, f[cur ^ 1][1] + 1}): min({f[cur ^ 1][2] + (t[i - 1] == '1'), f[cur ^ 1][1] + (t[i - 1] == '0') + 1, f[cur ^ 1][0] + (s[i - 1] == t[i - 1]) + 1});
			}
			printf ("%d\n", min({f[n & 1][0], f[n & 1][1], f[n & 1][2]}));
		}
		return 0;
	}
}

int main () {
	string str = "";
//	freopen((str + ".in").c_str(), "r", stdin);
//	freopen((str + ".out").c_str(), "w", stdout);
	Main::main();
	return 0;
}