Minimum Operations to Sort a String

Problem Statement:

You are given a string s of length n. In a single operation, you may remove any one character from s. Your task is to determine the minimum number of removal operations required to transform the string into one that is sorted in non-decreasing order.

Formally, let L be the length of the longest subsequence of s that is already in sorted order (i.e. the longest common subsequence between s and the string obtained by sorting the characters of s). Then the answer is given by:

$$ n - L $$

where n is the length of s.

You need to process T independent test cases.

inputFormat

Input Format:

The input is provided via standard input (stdin) and is structured as follows:

• The first line contains an integer T — the number of test cases.
• For each test case, there are two lines:
• The first line contains a single integer n, the length of the string.
• The second line contains the string s.

outputFormat

Output Format:

For each test case, output a single integer on a new line — the minimum number of operations (removals) required to convert the string into one that is sorted in non-decreasing order.

The result for each test case should be printed to standard output (stdout).

## sample

1
1
a

0

</p>