I. Daniel Saves Yash
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Due to an unfortunate incident in math class, Yash developed a severe fear of palindromes. However, evil Andrew decided to send him a string $$$S$$$ possibly containing palindromes as a gift! To protect his friend, Daniel intercepts the delivery and ensures that there is no presence of palindromes by removing all of them.

In an operation, Daniel can remove a substring of $$$S$$$ that is a palindrome with length greater than one. Note that removing a substring may result in more palindromic substrings, which may be removed later.

Given the gift, a string $$$S$$$ of length $$$N$$$, let $$$C$$$ be the maximum number of characters that can be removed by Daniel. Let $$$R$$$ be the minimum number of operations needed to achieve $$$C$$$ characters removed. Find $$$C$$$ and $$$R$$$.

Input

The first line contains $$$N$$$, the length of the string.

The second line contains $$$S$$$, the string.

It is guaranteed that $$$|S|=N$$$, and $$$1\leq N\leq 500$$$.

The string only contains lowercase Latin letters.

Output

Output two lines:

The first line contains $$$C$$$, the maximum number of characters removed by Daniel.

The second line contains $$$R$$$, the minimum number of removals needed to achieve $$$C$$$ characters removed.

Examples
Input
1
a
Output
0
0
Input
10
wqzzldajsw
Output
2
1
Input
6
abbcax
Output
5
2
Note

In the first example, no characters can be removed.

In the second example, only the substring zz can be removed.

In the third example, we can remove the substring bb. Then, the string becomes acax, and we can remove the substring aca. In total, we have removed $$$C=5$$$ characters in $$$R=2$$$ operations.