Longest Palindromic Subsequence of Digits

You are given a list of non-negative integers. For each integer, consider its decimal representation as a string of digits. Your task is to determine the length of the longest palindromic subsequence that can be formed from these digits.

A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements. A palindrome is a sequence that reads the same forwards and backwards.

You can solve this problem using dynamic programming. One common approach uses a 2D array dp where each element \(dp[i][j]\) represents the length of the longest palindromic subsequence in the substring from index \(i\) to \(j\). The state transition is given by:

[ \text{dp}[i][j] = \begin{cases} \text{dp}[i+1][j-1] + 2, & \text{if } s[i] = s[j], \ \max(\text{dp}[i+1][j],; \text{dp}[i][j-1]), & \text{if } s[i] \neq s[j]. \end{cases} ]

Your program should read input from stdin and output the result to stdout as described below.

inputFormat

The input starts with an integer (T) ((1 \le T \le 10^5)), representing the number of test cases. Each of the following (T) lines contains one non-negative integer.

outputFormat

For each test case, output a single line containing the length of the longest palindromic subsequence of the digits of the given integer.## sample

3
12321
45654
98789

5
5
5