Problem Description

Byteasar is addicted to the English letter 'q'. Now he comes across a string $S$ consisting of lowercase English letters.

He wants to find all the continous substrings of $S$, which only contain the letter 'q'. But this string is really really long, so could you please write a program to help him?

Input

The first line of the input contains an integer $T(1\leq T\leq10)$, denoting the number of test cases.

In each test case, there is a string $S$, it is guaranteed that $S$ only contains lowercase letters and the length of $S$ is no more than $100000$.

Output

For each test case, print a line with an integer, denoting the number of continous substrings of $S$, which only contain the letter 'q'.

2
qoder
quailtyqqq

1
7