AT_bogosortcontest_div2_c tatesoto string

長さ $ 3 $ 以上の文字列 $ X $ は以下の $ 2 $ つの条件を満たすとき、**tatesoto 文字列**であるといいます。 - $ X $ の先頭の $ 3 $ 文字は回文である。 - $ X $ の末尾の $ 3 $ 文字は回文である。 例えば、`tatesoto` は tatesoto 文字列ですが、`jastaway` は tatesoto 文字列ではありません。 英小文字からなる文字列 $ S $ が与えられます。 $ S $ の長さ $ 3 $ 以上 $ K $ 以下の部分文字列のうち、tatesoto 文字列であるようなものの個数を求めてください。 ただし、同じ文字列でも取り出す場所が異なる場合、別の部分文字列として数えます。 $ T $ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

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

答えを合計 $ T $ 行で出力せよ。 $ t $ 行目には、 $ t $ 番目のテストケースの答えを出力せよ。

### Sample Explanation 1 $ 1 $ つ目のテストケースについて、以下の $ 3 $ つの部分文字列が tatesoto 文字列となります。 - $ S $ の $ 2 \sim 4 $ 文字目を抜き出した `ogo` - $ S $ の $ 4 \sim 6 $ 文字目を抜き出した `oso` - $ S $ の $ 2 \sim 6 $ 文字目を抜き出した `ogoso` このうち、長さが $ 4 $ 以下であるものは最初の $ 2 $ つです。 $ 2 $ つ目のテストケースについて、以下の $ 3 $ つの部分文字列が tatesoto 文字列となります。 - $ S $ の $ 1 \sim 3 $ 文字目を抜き出した `tat` - $ S $ の $ 6 \sim 8 $ 文字目を抜き出した `oto` - $ S $ の $ 1 \sim 8 $ 文字目を抜き出した `tatesoto` これら $ 3 $ つとも、長さは $ 8 $ 以下です。 $ 3 $ つ目のテストケースについて、以下の $ 1 $ つの部分文字列が tatesoto 文字列となります。 - $ S $ の $ 5 \sim 7 $ 文字目を抜き出した `awa` この部分文字列の長さは $ 3 $ であり、 $ 6 $ 以下です。 $ 4 $ つ目のテストケースについて、 $ S $ の部分文字列で tatesoto 文字列となるものはありません。 ### Constraints - $ 1 \leq T \leq 10^5 $ - $ S $ は英小文字からなる文字列 - $ 3 \leq |S| \leq 5 \times 10^5 $ - $ 3 \leq K \leq |S| $ - すべてのテストケースについての $ |S| $ の総和は $ 5 \times 10^5 $ 以下 - 入力される数値はすべて整数