Fxx and string

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 131072/65536 K (Java/Others)

Description

Young theoretical computer scientist Fxx get a string which contains lowercase letters only.

The string $S$ contains $n$ lowercase letters $S_1S_2\ldots S_n$.Now Fxx wants to know how many three tuple $(i,j,k)$ there are which can meet the following conditions:

1、$i, j, k$ are adjacent into a geometric sequence.

2、$S_i=$'$y$'$,S_j=$'$r$'$,S_k=$'$x$'.

3.Either j|i or j|k

Input

In the first line, there is an integer $T(1\leq T\leq100)$ indicating the number of test cases.

$T$ lines follow, each line contains a string, which contains only lowercase letters.(The length of string will not exceed $10000$).

Output

For each case, output the answer.

Sample Input

2 xyyrxx yyrrxxxxx

Sample Output

0 2

Hint

wange2014

Source

BestCoder Round #89

提交代码