Given a line of text, output the longest contiguous substring that is an approximate palindrome. An approximate palindrome is defined as a string $S$ that satisfies the following conditions:

1. $S$ starts and ends with a letter.
2. $a(S)$ and $b(S)$ differ in at most $2k$ positions, where $a(S)$ is the string obtained by removing all non-letter characters from $S$ and converting all letters to lowercase, and $b(S)$ is the reverse of $a(S)$.

For example, when $k=1$, "Race cat" is an approximate palindrome because $a(S) = \text{"racecat"}$ and $b(S) = \text{"tacecar"}$ differ in exactly 2 positions.

Input

The input contains no more than 25 test cases. Each test case consists of two lines. The first line is an integer $k$ ($0 \le k \le 200$), and the second line is a string $S$, which contains at least one letter and no more than 1000 characters (excluding the newline character). $S$ contains letters, spaces, and other printable characters (such as commas and periods), and will not start with a whitespace character.

Output

For each test case, output the length and the starting position of the longest approximate palindrome substring (the first character of $S$ is at position 1). If there are multiple longest approximate palindrome substrings, choose the one with the smallest starting position.

Examples

Input 1

1
Wow, it is a Race cat!
0
abcdefg
0
Kitty: Madam, I'm adam.

Output 1

Case 1: 8 3
Case 2: 1 1
Case 3: 15 8