Description

许多人一定很熟悉九连环（如下图），九个环被串在一起，操作规则如下：第一个（右边）环可以任意装卸，如果第k个环没有被卸掉，而第k个环前边（右边）的所有环都被卸掉，则第k+1个环（第k个环左边的环）可以任意装卸（如果存在的话）。

用0表示此换被卸掉，1表示此环没有被卸掉，则九连环的每个状态可以用一个长度为9的二进制串来表示，如：111111001经过一次操作可以变成111111000，也可以变成111111011，111111111经过一次操作可以变成111111110，也可以变成111111101。

任务描述：

你现在要操作的是一个n连环，n为正整数，给出n连环的两种状态，计算出从第一种状态变换到第二种状态所需要的最少步数。

Input

第一行是一个正整数m，表示有m组测试数据。

每组测试数据一共3行，第一行是一个正整数n (0 < n < 128)，后两行每一行描述一种状态，n个数（0或1），用空格隔开。

Output

对于每一组测试数据输出一行，一个非负整数，表示从第一种状态变换到第二种状态所需要的最少步数。

2
3
0 0 0
1 0 0
4
1 0 0 0
0 1 1 0

7
11

Source

qinlu@POJ