Reference: Codeforces 1520E — Arranging The Sheep

A level is represented by a string of length ~n~ containing:

• * for a cell occupied by a sheep;
• . for an empty cell.

In one move, you may move one sheep one position to the left or right, provided that the destination cell exists and is empty.

Your goal is to place all sheep in consecutive cells, so that there are no empty cells between any two sheep.

For each test case, find the minimum number of moves required.

Input

• The first line contains one integer ~t~, the number of test cases.
• Each test case contains:
  • one integer ~n~;
  • one string ~s~ of length ~n~.

Output

• For each test case, print the minimum number of moves required.

Constraints

• ~1 \le t \le 10^4~
• ~1 \le n \le 10^6~
• ~s~ consists only of . and *
• The sum of ~n~ over all test cases does not exceed ~10^6~.

Example 1

Input:

5
6
**.*..
5
*****
3
.*.
3
...
10
*.*...*.**

Output:

1
0
0
0
9