問題文

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$ は整数

入力例 1Copy

babaabbabab
4
abab
b
babaabba
aaaaaaaaaaab

出力例 1Copy

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 の手順で達成可能です。