小蓝用黑白棋的 n 个棋子排成了一行，他在脑海里想象出了一个长度为 n 的 01 串 T。 他发现如果把黑棋当做1，白棋当做0，这一行棋子也是一个长度为 n 的 01 串 S 。 小蓝决定，如果在 S 中发现一个棋子和它两边的棋子都不一样，就可以将其翻转变成另一个颜色。 也就是说，如果S 中存在子串101 或者010，就可以选择将其分别变为 111 和 000，这样的操作可以无限重复。 小蓝想知道最少翻转多少次可以把 S 变成和 T 一模一样。
输入格式
输入包含多组数据。 输入的第一行包含一个正整数 D 表示数据组数。 后面 2D 行每行包含一个 01 串，每两行为一组数据。 第 2i－1 行为第 i 组数据的Ti，第 2i 行为第 i 组数据的Si，Si 和 Ti 长度均为 ni。 对于所有评测用例ni之和不超过1000000，ni ＞ 0。