Longest Palindromic Subsequence

Given a string \( s \), determine the length of the longest palindromic subsequence within \( s \). A palindromic subsequence is a sequence of characters from \( s \) (not necessarily contiguous) that reads the same forwards and backwards.

This problem requires an efficient dynamic programming solution. You will be given multiple test cases; for each test case, output the length of the longest palindromic subsequence found.

inputFormat

The first line of input contains an integer \( t \) — the number of test cases. The following \( t \) lines each contain a single string \( s \) for which you must compute the answer.

outputFormat

For each test case, print a single integer representing the length of the longest palindromic subsequence in \( s \). Each output should be on a new line.

3
bbbab
cbbd
abcba

4
2
5