A. Two Subsequences
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a string $$$s$$$. You need to find two non-empty strings $$$a$$$ and $$$b$$$ such that the following conditions are satisfied:

  1. Strings $$$a$$$ and $$$b$$$ are both subsequences of $$$s$$$.
  2. For each index $$$i$$$, character $$$s_i$$$ of string $$$s$$$ must belong to exactly one of strings $$$a$$$ or $$$b$$$.
  3. String $$$a$$$ is lexicographically minimum possible; string $$$b$$$ may be any possible string.

Given string $$$s$$$, print any valid $$$a$$$ and $$$b$$$.

Reminder:

A string $$$a$$$ ($$$b$$$) is a subsequence of a string $$$s$$$ if $$$a$$$ ($$$b$$$) can be obtained from $$$s$$$ by deletion of several (possibly, zero) elements. For example, "dores", "cf", and "for" are subsequences of "codeforces", while "decor" and "fork" are not.

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

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

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 1000$$$). Description of the test cases follows.

The first and only line of each test case contains one string $$$s$$$ ($$$2 \le |s| \le 100$$$ where $$$|s|$$$ means the length of $$$s$$$). String $$$s$$$ consists of lowercase Latin letters.

Output

For each test case, print the strings $$$a$$$ and $$$b$$$ that satisfy the given conditions. If there are multiple answers, print any.

Example
Input
3
fc
aaaa
thebrightboiler
Output
c f
a aaa
b therightboiler
Note

In the first test case, there are only two choices: either $$$a =$$$ f and $$$b = $$$ c or $$$a = $$$ c and $$$b = $$$ f. And $$$a = $$$c is lexicographically smaller than $$$a = $$$ f.

In the second test case, a is the only character in the string.

In the third test case, it can be proven that b is the lexicographically smallest subsequence of $$$s$$$. The second string can be of two variants; one of them is given here.