AT_abc462_f [ABC462F] More ABC

英大文字のみからなる文字列 $ S $ が与えられます。 高橋君の目標は、 $ S $ の文字のうちいくつかを置換することによって、 $ S $ が `ABC` を部分文字列として含む個数をちょうど $ K $ 個 **増やす** ことです。 このようなことが可能か判定し、可能な場合は目標を達成するために高橋君が最低何文字置換する必要があるか求めてください。 $ T $ 個のテストケースが与えられるので、それぞれについて答えを求めてください。 置換とは $ S $ の文字のうちの $ 1 $ つを置換するとは、 $ 1\leq i\leq \lvert S\rvert $ をみたす整数 $ i $ を $ 1 $ つ選び、 $ S $ の $ i $ 文字目を任意の英大文字 **$ 1 $ 字** で置き換えることを指します。 ただし、 $ \lvert S\rvert $ で $ S $ の長さを表すものとします。 部分文字列とは $ S $ の部分文字列とは、 $ S $ の先頭および末尾からそれぞれ $ 0 $ 文字以上削除して得られる文字列のことを指します。 $ 2 $ つの部分文字列は、 $ S $ から取り出した場所が異なれば、文字列として等しくとも区別して数えられます。

入力は以下の形式で標準入力から与えられる。 > $ T $ $ \mathrm{case}_1 $ $ \mathrm{case}_2 $ $ \vdots $ $ \mathrm{case}_T $ $ \mathrm{case}_i $ は $ i $ 番目のテストケースを表す。 各テストケースは以下の形式で与えられる。 > $ S $ $ K $

$ T $ 行出力せよ。 $ i $ 行目 $ (1\leq i\leq T) $ には、 $ i $ 個目のテストケースに対する答えを出力せよ。 ここで、各テストケースに対する答えとして、高橋君が目標を達成することが不可能な場合は $ -1 $ を、そうでない場合は目標を達成するために置換する必要のある文字の個数の最小値を出力せよ。

### Sample Explanation 1 $ 1 $ 個目のテストケースにおいて、与えられる文字列 $ S= $ `ATCABC` は `ABC` を部分文字列として $ 1 $ つ含んでいます。 $ S $ の $ 2 $ 文字目を `B` に置換すると、 $ S= $ `ABCABC` となって、`ABC` を部分文字列として $ 2 $ つ含むようになります。 これにより、 $ 1 $ 字置換することで、 `ABC` を部分文字列として含む個数が $ 1 $ つ増え、目標は達成されました。よって、 $ 1 $ 行目には $ 1 $ を出力します。 $ 2 $ 個目のテストケースにおいて、与えられる文字列 $ S= $ `ABABC` は `ABC` を部分文字列として $ 1 $ つ含んでいますが、 $ S $ の文字をどのように置換しても、 $ S $ が `ABC` を部分文字列として $ 2 $ つ含むようにすることはできません。 よって、 $ 2 $ 行目には $ -1 $ を出力します。 $ 3 $ 個目のテストケースにおいて、与えられる文字列 $ S= $ `XABCYZ` は `ABC` を部分文字列として $ 1 $ つ含んでいます。 $ S $ が `ABC` を部分文字列として $ 2 $ つ含むようにするためには、 $ S $ の全ての文字を置換し、 $ S= $ `ABCABC` とする必要があります。 よって、 $ 3 $ 行目には $ 6 $ を出力します。 ### Constraints - $ 1\leq T\leq 10^5 $ - $ S $ は英大文字のみからなる長さ $ 3 $ 以上 $ 3\times 10^5 $ 以下の文字列 - $ 1\leq K \leq 10 $ - それぞれの入力において、各テストケースの $ S $ の長さの総和は $ 3\times 10^5 $ 以下である。 - $ T,K $ は整数