AT_qupc2018_j Repeat Strings

[problemUrl]: https://atcoder.jp/contests/qupc2018/tasks/qupc2018_j `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 $ に一致させるために必要な操作回数の最小値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ S $ $ Q $ $ T_1 $ $ T_2 $ $ : $ $ T_Q $

$ Q $ 行出力せよ。$ 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 $ は整数 ### Sample Explanation 1 それぞれの $ T'_i $ は次の通りです。 - $ T'_1\ = $ `abababababa` - $ T'_2\ = $ `bbbbbbbbbbb` - $ T'_3\ = $ `babaabbabab` - $ T'_4\ = $ `aaaaaaaaaaa` 例えば $ S $ を $ T'_1 $ に一致させるために必要な操作回数の最小値は $ 2 $ です。`babaabbabab` → `ababbaababa` → `abababababa` の手順で達成可能です。