Palindromlar fabriki

Təsadüfi bir $\text{g}$ sətrini nəzərdən keçirək. Bu sətri palindrom yaradan adlandıraq. Bu sətrin yaratdığı palindromlar çoxluğu $\text{P(g)}$ aşağıdakı kimi təyin olunur:

Sətrin uzunluğu $n$-dir. Hər bir $i$ üçün ($1$-dən $n$-ə qədər), g[1..i]g[1..i]^r və g[1..i]g[1..i-1]^r sətləri $\text{P(g)}$ çoxluğuna daxildir. Burada, \alpha^r $\alpha$ sətrinin tərs yazılışı deməkdir.

Məsələn, əgər g = \text{olymp} olsa, onda P(g) = \{\text{oo}, \text{o}, \text{ollo}, \text{olo}, \text{olyylo}, \text{olylo}, \text{olymmylo}, \text{olymylo}, \text{olymppmylo}, \text{olympmylo}\} olacaq.

Palindrom yaradan $g$ və sətir $s$ verilib. Müəyyən edin ki, $P(g)$-yə aid olan sətirlər $s$ daxilində neçə dəfə alt-sətir kimi yerləşir. Başqa sözlə, neçə $(i,j)$ cütlüyü var ki, s[i..j] \in P(g).