Longest Palindromic Subsequence

In this problem, you are given a string (s) consisting of lowercase English letters, and you need to determine the length of the longest palindromic subsequence within it. A subsequence is a sequence that can be derived from the string by deleting some or no elements without changing the order of the remaining characters. A palindrome is a string that reads the same forwards and backwards.

For example, given the string "abca", one of the longest palindromic subsequences is "aca", which has a length of 3.

The problem will contain multiple test cases. You are required to process the input from standard input (stdin) and write the results to standard output (stdout), one result per line.

inputFormat

The first line of input contains an integer (T) representing the number of test cases. Each test case consists of two lines: the first line contains an integer (n) denoting the length of the string, and the second line contains the string (s) (consisting only of lowercase English letters).

outputFormat

For each test case, output a single integer representing the length of the longest palindromic subsequence in the given string. Each result should be printed on a new line.## sample

3
4
abca
6
abcdef
3
aaa

3
1
3