Given a string ~s~, find the length of the longest subsequence of ~s~ that is a palindrome.

A subsequence is formed by deleting zero or more characters without changing the order of the remaining characters. A palindrome reads the same forwards and backwards.

Input

The first line contains an integer ~n~, the length of the string.

The second line contains the string ~s~.

Output

Output one integer: the length of the longest palindromic subsequence of ~s~.

Constraints

• ~1 \le n \le 5000~
• ~s~ consists only of lowercase English letters.

Subtasks

• For 20 points, ~n \le 20~.
• For 30 points, ~n \le 500~.
• For 50 points, no additional constraints.

Example 1

Input

5
bbbab

Output

4

Explanation

One longest palindromic subsequence is bbbb.

Example 2

Input

4
cbbd

Output

2

Explanation

One longest palindromic subsequence is bb.

Example 3

Input

6
agbdba

Output

5

Explanation

One longest palindromic subsequence is abdba.