K. Kuusi Seitsemän
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Six seven. Six seven. 67, 67, 67.

"It's joever; pack it up," you thought. The brainrot trend has gone too far. It is the end of society.

First they came as skibidi toilet, and you did not speak out. Because you thought that was fine. Then they came as tralalero tralala, and you did not speak out. Because you thought that was nonsense. Then they released the game Tung Tung Sahur Extreme, and you did not speak out. Because you thought no one cared about that. Then they came as six seven, and there was no one left to speak for you. The problem title itself, you realized, it means "six seven" in Finnish. You are finished.

All that is left, is a string. You are given a string $$$S$$$. It can contain three different characters: six (6), seven (7), and — if you think that's enough, it is not — ASCII code 67: upper case Latin alphabet C.

This is your final chance. Even if it might be futile, you would still want to try for the very last time. You must replace each ASCII code 67 character with one of six (6) or seven (7). Your goal is to minimize the number of subsequences of the string that are identical to six seven (67).

Two subsequences are considered different if there exists at least one position that is in one but not the other.

Input

The first line contains a single integer $$$t$$$, indicating the number of test cases. Next, $$$t$$$ lines follows. Each test case consists of single line containing the string $$$S$$$.

  • $$$1 \leq t \leq 10^5$$$
  • $$$1 \leq |S|$$$
  • The sum of the lengths of all strings $$$S$$$ does not exceed $$$5 \times 10^5$$$.
  • Each character of $$$S$$$ is either 6 or 7, or has ASCII code 67.
Output

For each test case, output one line containing an integer, indicating the minimum number of subsequences that are identical to 67 after substituting all character with ASCII code 67.

Example
Input
5
67CCC67
67C7CC67
6666C6767CC6C6C67777
66766676677677C67C77
66666666666766766C6666666C6677C77776777777C77677777777777
Output
6
7
67
69
727