放鞭炮
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

春节放鞭炮是中国传统的习俗之一，它源自古代驱邪的仪式，人们相信鞭炮的声音能够驱赶邪灵，带来好运和吉祥。在春节期间，人们会在家门口或者庭院里放鞭炮，以祈求新的一年平平安安、吉祥如意。放鞭炮的习俗也有着丰富的文化内涵，它象征着对新年的热烈祝福和对传统文化的尊重。然而，随着城市化进程和环保意识的提高，一些地方已经出台了禁放鞭炮的政策，以减少空气污染和噪音干扰。总的来说，春节放鞭炮是中国传统文化的一部分，虽然在一些地方受到了限制，但它依然是春节期间不可或缺的重要习俗之一。
                        

很怕放鞭炮，所以就故意放鞭炮来吓唬他！经过长时间的锻炼，现在已经可以通过超能力来改变鞭炮的爆炸状态。我们将鞭炮抽象为一个图形，如图所示。每个位置上可以有两种状态表示，已经爆炸为，未爆炸为。的超能力表现为如果更改一个位置的状态，那么与它相邻边的位置的爆炸状态也会同步更改，即。现在给定一个鞭炮爆炸的状态，请你帮助计算出他至少需要发动的超能力次数以使得鞭炮的爆炸状态到一个自己不害怕的爆炸状态。
                                                 

输入描述:

第一行一个整数，代表数据组数。
接下来组数据，每组数据行，分别为个字符串,输入的顺序为给定图中ABCDEF的顺序，第一个字符串代表鞭炮的初始状态，第二个代表不害怕的鞭炮爆炸状态。
数据范围：

输出描述:

共行，如果可以改变鞭炮爆炸状态到不害怕的状态，输出一个最小操作次数，否则输出。
示例1

输入

复制 
2
000001
010100
000101
001010

输出

复制 
2
1