C. Six and Seven
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Templates for this problem are available here.

Alice loves the number "67". On her birthday, Bob gifts her a string $$$s$$$ consisting only of 6's and 7's. Alice is pleased, but she also wants to know how many ways she can choose one 6 and one 7 such that the 7 appears after the 6. Help her figure this out.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

Each test case contains a single string $$$s$$$ ($$$1 \le |s| \le 2 \cdot 10^5$$$, where $$$|s|$$$ is the length of the string $$$s$$$), consisting only of characters 6 and 7.

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

Output

For each test case, output one integer — the number of ways to choose one 6 and one 7.

Example
Input
4
767
677
6767
777
Output
1
2
3
0
Note

In the first test case, there is only $$$1$$$ way: choose the second and third characters.

In the second test case, there are $$$2$$$ ways: choose the first and second characters, or choose the first and third characters.