E. Partition of a Binary String
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given a binary string $$$s$$$ of length $$$n$$$. The characters of the string are numbered from $$$1$$$ to $$$n$$$.

You have to partition all integers from $$$1$$$ to $$$n$$$ into nonempty sets so that each integer belongs to exactly one set. For each pair of distinct integers $$$x$$$ and $$$y$$$ in the same set, at least one of the following conditions must hold:

  • $$$s_x = s_y$$$;
  • $$$|x-y| = 1$$$.

For a set $$$M$$$, let $$$f(M)$$$ be the number of distinct characters among $$$s_x$$$ over all $$$x \in M$$$. The cost of the set $$$M$$$ is $$$|M| \cdot f(M)$$$, where $$$|M|$$$ is the number of elements in $$$M$$$. The cost of a partition is the sum of the costs of all its sets.

For example, if the string $$$s$$$ is 10001000, the partition into the sets $$$\{1, 2\}, \{3, 8\}, \{4, 5, 6\}, \{7\}$$$ is valid, and its cost is $$$2 \cdot 2 + 2 \cdot 1 + 3 \cdot 2 + 1 \cdot 1 = 13$$$.

Find the maximum possible cost of a partition and the number of partitions with this cost. Partitions that differ only in the order of the sets or the order of elements within the sets are considered the same. Output the number of partitions modulo $$$998\,244\,353$$$.

Input

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

The first line of each test case contains one integer $$$n$$$ ($$$1 \le n \le 5000$$$) — the length of the string.

The second line of each test case contains one string $$$s$$$ of length $$$n$$$, consisting only of the characters 0 and 1.

Output

For each test case, print two integers: the maximum cost of a partition and the number of partitions with this cost (taken modulo $$$998\,244\,353$$$).

Example
Input
3
8
10001000
6
000111
8
01010101
Output
13 5
8 4
16 4