E. Cringemeter
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
Input

You'll be given a number $$$t$$$ which shows the number of test cases.

$$$$$$1 \le t \le 10^4$$$$$$

For each test case you will receive a single string of lowercase latin letters $$$s$$$.

$$$$$$1 \le |s| \le 2 \cdot 10^5$$$$$$

It's guaranteed that sum of lengths over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, print one integer $$$-$$$ the answer.

Example
Input
25
cringe
cringecringe
ccrriinnggee
aaaaaaaaaaaaaaaa
bbbbbbbbbbbbbbbb
djjj
jdjj
jjdj
jjjd
lettersum
kirito
abcdef
impossible
orzorzorzorzorzorz
divide
codeforces
codechef
leetcode
atcoder
theforces
minecraft
modten
sahidhsdbfsdoftbfhg
groitoeortgdnfgjjniub
crineorngoeirndofgmd
Output
1
2
2
0
0
1
1
1
1
1
1
0
1
3
0
1
1
1
0
1
1
0
3
3
3