Longest Palindromic Subsequence in a Binary String

You are given a binary string s consisting of only the characters '0' and '1'. Your task is to determine the maximum length of a subsequence of s that forms a palindrome.

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

For example, in the string "10101", the whole string is a palindrome, so the answer is 5. In the string "1100", one possible palindromic subsequence is "11" or "00", so the answer is 2.

Your solution should process multiple test cases.

inputFormat

The first line of input contains an integer t \( (1 \leq t \leq 10^5) \) denoting the number of test cases.

Each of the next t lines contains a binary string s \( (1 \leq |s| \leq 10^5) \) consisting only of the characters '0' and '1'.

outputFormat

For each test case, output a single integer on a new line -- the maximum length of a palindromic subsequence of the given binary string.

## sample

3
1100
10101
10001

2
5
5

</p>