Given a string "s" consisting only of lowercase English letters, find the length of its Longest Palindromic Subsequence (LPS).

A subsequence is obtained by deleting zero or more characters from the string while preserving the relative order of the remaining characters.

The selected characters do not need to be contiguous.

A palindrome reads the same from left to right and right to left.

Examples

Input| Output ""ba""| "1" ""aaa""| "3" ""bandana""| "5"

Example 1

For:

s = "ba"

Possible palindromic subsequences include:

"b" "a"

Hence, the longest palindromic subsequence has length:

1

Example 2

For:

s = "aaa"

The entire string is already a palindrome:

"aaa"

Therefore:

Answer = 3

Example 3

For:

s = "bandana"

One longest palindromic subsequence is:

"anana"

Therefore:

Answer = 5

Constraints

• "1 ≤ n ≤ 5000"
• "s" contains only lowercase English letters.

Expected Complexity

The intended solution should run in:

Time: O(n²) Space: O(n)

An "O(n²)" space solution may be possible using the standard interval DP, but the preferred solution should optimize the memory usage to O(n).

Output

Return a single integer representing the length of the Longest Palindromic Subsequence of "s".