Longest Palindromic Subsequence

Given a string ( s ), your task is to determine the length of the longest palindromic subsequence in ( s ). 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 elements. A palindromic subsequence is one that reads the same backward as forward.

For example, given the string bbbab, one valid longest palindromic subsequence is bbbb which has a length of 4. Your program should be able to handle multiple test cases.

inputFormat

The first line of input contains an integer ( T ) representing the number of test cases. Each of the following ( T ) lines contains a non-empty string ( s ) consisting of lowercase letters.

outputFormat

For each test case, output a single line representing the length of the longest palindromic subsequence in the corresponding string.## sample

2
bbbab
cbbd

4
2