Ahmed Gafer failed to pass the test, but he got the job because of his friendship with Said and Shahhoud. After working in the kitchen for a while, he blew it. The customers didn't like the food anymore and one day he even burned the kitchen. Now the master Chef is very upset.
Ahmed isn't useful anymore at being a co-Chef, so S&S decided to give him a last chance. They decided to give Ahmed a new job, and make him work as the cashier of the restaurant. Nevertheless, in order not to repeat their previous mistake, they decided to give him a little test to check if his counting skills are good enough for the job. The problem is as follows: 
Given a string A of lowercase English letters, Ahmad was asked to find the number of good substrings.
A substring A[L, R] is good if:

-  The length of the substring is exactly 2 and AL = AR, OR
- The length of the substring is greater than 2,AL = AR and the substring A[L + 1, R - 1] has only one distinct letter.

Anyways, Ahmed struggled trying to find a solution for the problem. Since his mathematical skills are very poor as it turned out, he decided to cheat and contacted you asking for your help. Can you help him in this challenge?

-----Input-----
The first line of the input contains the integer T, indicating the number of test cases.
Each of the following T lines, contains a string A.

-----Output-----
For each test case, output a single line containing a single number, indicating the number of good substrings.

-----Constraints-----

- 1 ≤ T ≤ 100 
- 1 ≤  |A|  ≤ 105 
-  It's guaranteed that the sum of  |A|  over all test cases doesn't exceed 5x105. 

-----Example-----
Input:
2
a
abba

Output:
0
2


-----Explanation-----
Example case 2. The good substrings of abba are: { bb } and { abba }.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'e=10**9+7\nt=int(input())\nfor _ in range(t):\n s=input()\n ans=0\n n=len(s)\n i=1\n m=1\n while i<n and s[i]==s[i-1]:\n  m+=1\n  i+=1\n ans+=(m*(m-1))//2\n while i<n:\n  x=s[i-1]\n  i+=1\n  m=1\n  while i<n and s[i]==s[i-1]:\n   m+=1\n   i+=1\n  ans+=(m*(m-1))//2\n  if i!=n and s[i]==x:\n   ans+=1\n print(ans)\n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13279