問題文

a と b からなる文字列 S があって、以下の操作を好きな回数だけ行うことができます。

• S の連続する区間 [l, r] を選ぶ。l \leq k \leq r を満たすすべての整数 k に対し、S_k が a なら S_k を b に、S_k が b なら S_k を a に置き換える。

Q 個の 文字列 T_i が与えられます。各 T_i は a と b からなります。T_i を 10^{100} 回連結し |S|+1 文字目以降をすべて切り落とした文字列を T'_i とします。

それぞれの文字列 T'_i に対し、S を T'_i に一致させるために必要な操作回数の最小値を求めてください。

制約

• 1 \leq |S| \leq 2 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• 1 \leq |T_i| \leq 2 \times 10^5
• T_i の長さの合計は 2 \times 10^5 以下
• S, T_i は a と b からなる文字列
• Q は整数

入力例 1

babaabbabab
4
abab
b
babaabba
aaaaaaaaaaab

出力例 1

2
4
0
5

それぞれの T'_i は次の通りです。

• T'_1 = abababababa
• T'_2 = bbbbbbbbbbb
• T'_3 = babaabbabab
• T'_4 = aaaaaaaaaaa

例えば S を T'_1 に一致させるために必要な操作回数の最小値は 2 です。babaabbabab → ababbaababa → abababababa の手順で達成可能です。