You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

Monocarp is participating in a programming contest, which features 2626 problems, named from 'A' to 'Z'. The problems are sorted by difficulty. Moreover, it's known that Monocarp can solve problem 'A' in 11 minute, problem 'B' in 22 minutes, ..., problem 'Z' in 2626 minutes.

After the contest, you discovered his contest log — a string, consisting of uppercase Latin letters, such that the ii-th letter tells which problem Monocarp was solving during the ii-th minute of the contest. If Monocarp had spent enough time in total on a problem to solve it, he solved it. Note that Monocarp could have been thinking about a problem after solving it.

Input

The first line contains a single integer tt (1≤t≤1001≤t≤100) — the number of testcases.

The first line of each testcase contains a single integer nn (1≤n≤5001≤n≤500) — the duration of the contest, in minutes.

The second line contains a string of length exactly nn, consisting only of uppercase Latin letters, — Monocarp's contest log.

Output

For each testcase, print a single integer — the number of problems Monocarp solved during the contest.

Samples

3
6
ACBCBC
7
AAAAFPC
22
FEADBBDFFEDFFFDHHHADCC

3
1
4

Limitation

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output