D. Make It Minimum
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

ALI-SAIRO has a string $$$s$$$ of length $$$n$$$ containing only digit numbers from '0' to '9'.

Let's define $$$d_i \ (1 \le i \lt n)$$$ as the number whose decimal representation is $$$s_is_{i+1}$$$.

We define $$$F$$$ as: $$$$$$F(s) = \sum_{i=1}^{n-1}d_i$$$$$$

For example : $$$s$$$ = "0130" then $$$F = 01 + 13 + 30 = 44$$$.

In one operation, you can choose $$$i$$$ and $$$j \: (1 \le i \le j \le n)$$$; ($$$i, \ j$$$ don't have to be adjacent), and swap $$$s_i$$$ and $$$s_j$$$.

Find the minimum number of operations required to minimize $$$F(s)$$$, and determine the minimum value of $$$F(s)$$$.

Input

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

The first line of each test case contains a single integer $$$n :\ (1 \le n \le 10^6)$$$ — length of the string.

The second line of each test case contains a string $$$s$$$ of length $$$n$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$10^6$$$.

Output

For each testcase, output the minimum number of operations required to minimize $$$F(s)$$$, and determine the minimum value of $$$F(s)$$$.

Example
Input
3
2
21
8
99999999
1
9
Output
1 12
0 693
0 0