C. Largest Palindromic Subsequence
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

For a given string, find the lexicographically largest palindromic subsequence of the string.

A string $$$a$$$ is lexicographically smaller than a string $$$b$$$ if and only if one of the following holds:

  • $$$a$$$ is a prefix of $$$b$$$, but $$$a \ne b$$$;
  • in the first position where $$$a$$$ and $$$b$$$ differ, the string $$$a$$$ has a letter that appears earlier in the alphabet than the corresponding letter in $$$b$$$.

A string $$$t$$$ is a subsequence of a sequence $$$s$$$ if $$$t$$$ can be obtained from $$$s$$$ by the deletion of several (possibly, zero or all) elements.

Input

Each test contains multiple testcases. The first line contains the number of testcases $$$t$$$ ($$$1\leq t\leq 10^5$$$). This is followed by $$$t$$$ lines — the description of the testcases.

Each line contains a single string $$$s$$$ ($$$1\leq \lvert s\rvert \leq 2\cdot 10^5$$$) — the string to find the lexicographically largest palindromic subsequence of. The string will only contain lowercase latin letters.

It is guaranteed that the sum of $$$\lvert s\rvert$$$ over all testcases does not exceed $$$5\cdot 10^5$$$.

—

Testcases in subtasks are numbered $$$1$$$ to $$$20$$$ with samples skipped.

Test $$$1-5$$$: The sum of $$$\vert s\rvert$$$ does not exceed $$$5\cdot 10^3$$$.

Test $$$6-20$$$: No additional constraints.

Each test is worth $$$5$$$ points with samples skipped.

Output

For each test case, print a string — the lexicographically greatest palindromic subsequence.

Example
Input
4
k
aoeu
bbabaa
acreativesamplecase
Output
k
u
bbb
v
Note

— Problem Idea: dutin Problem Preparation: dutin Occurrences: Novice 3