I. Delete the String
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a string $$$s$$$ of length $$$n$$$. In one operation, you can select a substring $$$s[l \ldots r]$$$ ($$$1 \leq l \leq r \leq n$$$) and delete it from the string if and only if $$$s_l = s_r$$$.

Determine the minimum number of operations required to delete the entire string.

A string $$$a$$$ is a substring of a string $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.

Input

The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

For each test case, the first line contains an integer $$$n$$$ ($$$1 \le n \le 10^6$$$) — the length of the string and the second line contains a string $$$s$$$ of length $$$n$$$ consisting of only lowercase Latin letters.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$3 \cdot 10^6$$$.

Output

For each test case, print a single integer — the minimum number of operations required to delete the entire string.

Example
Input
4
6
acabdb
4
aaaa
18
abcdaecfacgahciajc
15
abcdaefcghijcki
Output
2
1
2
5
Note

In the first test case, one possible sequence of operations is first deleting the substring aca and then bdb.

In the second test case, the entire string can be deleted in a single operation since all characters are identical.