H. Halfway Hawser
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Mr. Nežmah found a large string of length $$$n$$$; in fact, it is so large it would be more appropriate to call it a hawser. However, he would like to remove exactly one letter from it. From the $$$n$$$ strings which can be obtained in such a way, he is interested in the lexicographic median.

Formally, let $$$t_i$$$ denote the string obtained by removing the $$$i$$$-th letter from $$$s$$$. Let $$$p$$$ be any permutation of numbers from $$$1$$$ to $$$n$$$ such that $$$t_{p_{i}}$$$ is lexicographically smaller than or equal to $$$t_{p_{i + 1}}$$$. He wants to know $$$t_{p_{\lfloor{\frac{n + 1}{2}}\rfloor}}$$$.

Input

The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 2 \cdot 10^4$$$), the number of test cases.

The only line of each test case contains a single string $$$s$$$ ($$$2 \leq |s| \leq 10^6$$$), consisting only of lowercase english characters.

The sum of $$$|s|$$$ across all test cases is at most $$$10^6$$$.

Output

For each test, in a single line, output the required string.

Example
Input
4
zagreb
klokani
oblutci
abc
Output
zagrb
klokan
oblutc
ac