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