Longest Palindromic Substring Finder

You are given a list of strings. For each string, find the longest palindromic substring. A palindrome is a string that reads the same forward and backward. In case of multiple palindromic substrings with the same maximum length, return the one that appears first in the string.

Your task is to produce, for each input string, a JSON object with the following keys:

• input: The original string.
• length: The length of the longest palindromic substring.
• substring: The longest palindromic substring itself.

The algorithm's complexity should ideally be efficient. You can use the expand-around-center approach to achieve the result.

Recall the definition of a palindrome: a string s is a palindrome if $$s = s^R,$$ where $$s^R$$ denotes the reverse of s.

inputFormat

The input is read from stdin and has the following format:

n
s1
s2
...
sn

Here, the first line is an integer $$n$$ representing the number of strings, followed by $$n$$ lines each containing a single string.

outputFormat

For each of the $$n$$ input strings, output a JSON object on a separate line. Each JSON object should have the following format:

{"input": "", "length": , "substring": ""}

The output should be written to stdout.

## sample

4
babad
cbbd
a
ac

{"input": "babad", "length": 3, "substring": "bab"}
{"input": "cbbd", "length": 2, "substring": "bb"}
{"input": "a", "length": 1, "substring": "a"}
{"input": "ac", "length": 1, "substring": "a"}

</p>