J. HCPC Nightmares
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

After waiting a long time for HCPC, Najjar began dreaming about it. One of his nightmares went as follows:

Najjar wants to type a target string $$$s$$$ from left to right. Normally, pressing a letter's key appends one copy of that letter to the text.

Because it is a dream, Najjar may choose at most one lowercase English letter and apply magic to its key. If he chooses a letter $$$c$$$, then every press of the $$$c$$$ key appends exactly two consecutive copies of $$$c$$$ instead of one. The magic cannot be disabled and is applied before he starts typing. All other keys continue to append one letter per press.

Najjar must obtain exactly $$$s$$$. What is the minimum number of key presses he needs?

Input

The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

Each test case consists of one string $$$s$$$ ($$$1 \le |s| \le 2\cdot 10^5$$$) containing only lowercase English letters.

The sum of $$$|s|$$$ over all test cases does not exceed $$$2\cdot 10^5$$$.

Output

For each test case, print one integer — the minimum number of key presses required to type $$$s$$$ exactly.

Example
Input
7
a
aa
aba
aabbaa
aaabbb
aabbcc
aaaaaa
Output
1
1
3
4
6
5
3