为了检验关于猫的假设,科学家们必须以特定的方式将猫排列在盒子里。当然,他们希望尽快检验这个假设并发表一篇轰动性的文章,因为他们太全神贯注于下一个关于手机电池电量的假设了。
科学家们有$$$n$$$个盒子,猫可以坐在里面,也可以不坐在里面。让盒子的当前状态由序列 $$$b_1, \dots, b_n$$$ 表示:如果 $$$i$$$ 盒子中有一只猫,则 $$$b_i = 1$$$,否则 $$$b_i = 0$$$。
幸运的是,猫的无限生产已经建立,所以有一天,科学家们可以执行以下操作之一:
- 拿一只新猫并将其放入盒子中(对于某些$$$i$$$,使得$$$b_i = 0$$$,分配$$$b_i = 1$$$)。
- 从盒子里取出一只猫并将其送去退休(对于某些$$$i$$$,使得$$$b_i = 1$$$,分配$$$b_i = 0$$$)。
- 将一只猫从一个盒子移到另一个盒子(对于某些 $$$i, j$$$,使得 $$$b_i = 1, b_j = 0$$$,分配 $$$b_i = 0, b_j = 1$$$)。
还发现一些箱子立即装满了猫。因此,科学家们知道盒子中猫的初始位置 $$$s_1, \dots, s_n$$$ 和所需位置 $$$f_1, \dots, f_n$$$。
由于大量的文书工作,科学家们没有时间解决这个问题。为了科学的目的帮助他们,并指出检验假设所需的最少天数。
输入
每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。接下来是测试用例的描述。
每个测试用例由三行组成。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) — 盒子的数量。
每个测试用例的第二行包含一个由 $$$n$$$ 个字符组成的字符串 $$$s$$$,其中如果第 $$$i$$$ 个框中有一只猫,则第 $$$i$$$ 个字符为“1”,否则为“0”。
每个测试用例的第三行包含一个由 $$$n$$$ 个字符组成的字符串 $$$f$$$,其中如果第 $$$i$$$ 个框中应该有一只猫,则第 $$$i$$$ 个字符为“1”,否则为“0”。
保证在一次测试中所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。
输出
对于每个测试用例,在单独的行上输出一个整数 - 从初始位置获得所需位置所需的最少操作数。可以证明,解总是存在的。
示例
输入 #1
6 5 10010 00001 1 1 1 3 000 111 4 0101 1010 3 100 101 8 10011001 11111110
输出 #1
2 0 3 2 1 4
注意
在第一个测试用例中,您可以先将猫从第一个盒子移动到第五个盒子,然后将猫从第四个盒子中移走。
在第二个测试用例中,没有什么可做的 - 唯一的猫已经坐在正确的盒子里。
在输入数据的第三个测试用例中,每个盒子里放一只猫需要三天的时间。