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⁶.