問題文

長さ 3 以上の文字列 X は以下の 2 つの条件を満たすとき、tatesoto 文字列であるといいます。

• X の先頭の 3 文字は回文である。
• X の末尾の 3 文字は回文である。

例えば、tatesoto は tatesoto 文字列ですが、jastaway は tatesoto 文字列ではありません。

英小文字からなる文字列 S が与えられます。 S の長さ 3 以上 K 以下の部分文字列のうち、tatesoto 文字列であるようなものの個数を求めてください。 ただし、同じ文字列でも取り出す場所が異なる場合、別の部分文字列として数えます。

T 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

• 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 以下
• 入力される数値はすべて整数

入力例 1

6
bogosort
4
tatesoto
8
jastaway
6
soryuusi
7
zzzzzzzzzz
8
welcometobogosortprogrammingcontest
21

出力例 1

2
3
1
0
33
6

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 文字列となるものはありません。