Bob is a construction worker who does mathematics for increasing his efficiency. He is working on a site and has $n$ buckets of cement lined up with different characters $(a - z)$ marked upon them. He has a strict command from the senior that he cannot change the order of the buckets.

Before starting his work, he has been given a string $s$ of length $n$ in which the character at position $i$ ($1 \le i \le n$) gives us the mark on the $i^{th}$ bucket. He can only carry one bucket at a time and bring it back to the base site. In each round, he has a criterion on which bucket to pick up. He will take the bucket with the smallest character marked upon it ($a < b < z$) and if there are multiple buckets with the smallest character, then he will take the one closest to the base.

The cost of picking up a bucket $B$ is the number of buckets he passes through while walking from the site to get $B$ (the bucket which he picks is also included). In each round, the cost accumulates. Find the final cost incurred by Bob while completing his job.

Input format

• The first line consists of an integer $t$ denoting the number of test cases.
• The following $t$ lines consist of an integer $n$ denoting the number of baskets.
• The next line contains a string $s$ of length $n$ where $S[i]$ ($1 \le i \le n$) denotes the mark on the $i^{th}$ bucket.

Output format

Print the accumulation cost for each test case separated by a new line.

Constraints

$1 \le  t ,\ n \le 10^5$

The sum of $n$ over all test cases does not exceed 10⁶.