F： 01 文字列と窓 (Binary String with Slit)

問題

文字の種類が 0 と 1 のみからなる文字列 S が与えられます。以下の操作を繰り返すことで、S を T に変えたいです。

• 文字列 S 中の最も右側に登場する 1 を含むように、幅 2 のスリットを置く。スリット内には連続した 2 文字を必ず含まなければならない。つまり、文字列の端 1 文字のみを含むように置くことはできない。2 通り置ける場合も考えられるが、この場合はどちらの方法で置いても構わない。

• スリット中の 2 文字を 2 桁の二進数と捉えるとき、元の数値との差の絶対値が 1 になるようにスリット中の文字を変更する。ただし、スリット中の文字の両方が 0 になってはならない。つまり、変更後のスリット内の数値は 1 から 3 までのいずれかとなる。

クエリが Q 回与えられます。i 番目のクエリで 1 を少なくとも一つ含む文字列 S_i, T_i が与えられるので、S_i を T_i に変えるために必要な操作回数の最小値を、それぞれのクエリについて求めてください。

入力形式

Q
S_1 T_1
...
S_Q T_Q

1 行目では、クエリの個数 Q が与えられる。

2 行目以降 Q 行は、クエリが与えられる。 i+1 行目では S_i と T_i が空白区切りで与えられる。

制約

• 1 \leq Q \leq 10^5
• 2 \leq |S_i| = |T_i| \leq 50
• S_i, T_i は 0 と 1 のみからなる文字列である。
• S_i, T_i はともに 1 を少なくとも 1 つ含む文字列である。

出力形式

出力は Q 行からなる。

i 行目には、i 番目のクエリに対する結果を出力せよ。

入力例1

4
101 110
101 101
1010 1101
11011001 10010101

出力例1

1
0
3
12

• 1 個目のクエリでは、S = 101 を T = 110 と一致させるために必要な操作回数の最小値を求める必要があります。以下の画像のように、 S の中に登場する 1 の中で最も右にあるものが含まれるようにスリットを置き、スリット中の文字列を書き換えることで 1 回の操作で S と T を一致させることができます。

• 2 個目のクエリでは、はじめから S と T が一致しているため、操作の必要がありません。
• 3 個目のクエリについて、以下の画像のように文字列を変更させると 3 回の操作で S と T を一致させることができます。