给你一串长度为18的01序列，它们的编号从左到右依次为1,2,3......16,17,18。
定义每一次参数为k（1<=k<=18）的翻转会把编号为k的倍数的几个位置同时进行翻转，即0变成1,1变成0。
给定一个初始状态和一个目标状态，问你最少需要几次翻转（每次翻转的k值可以任意选取）可以从起始状态达到目标状态。
最小翻转次数
Input
首先输入T，表示有T组测试用例。注意T会很大（100000<=T<=200000）
然后接下来每两行为一组测试用例，为两个长为18的01字符串，详见测试样例
然后接下来每两行为一组测试用例，为两个长为18的01字符串，详见测试样例
Output
对于每组测试用例，用一行输出最少翻转步数来从起始状态达到目标状态，如果不能达到，输出-1
Sample Input
3
000000000000000000
111111111111111111
000000000000000000
010101010101010101
000000000000000010
000000000000000000
Sample Output
1
1
1