Longest Palindromic Subsequence Problem Statement

Given a string A consisting of lowercase English letters, determine the length of the longest palindromic subsequence within A.

Explanation:

• A subsequence is derived from a string by deleting some or no characters without changing the order of the remaining characters.
• A string is a palindrome if it reads the same forwards and backwards (e.g., "abba").

Input:

The first line contains an integer ‘T’, indicating the number of test cases. Each test case consists of a single string ‘A’.

Output:

Output a single integer per test case, representing the length of the longest palindromic subsequence in ‘A’.

Example:

Input: 
 2
 bbabcbcab
 dcbccbcabbb
 
Output: 
 7
 7

Constraints:

• 1 <= T <= 10
• 1 <= N <= 10²
• Where ‘T’ represents the number of test cases and ‘N’ represents the length of the string.
• Time limit: 1 second.

Note:

No need to print anything; implement the function to obtain the result.