A. A.TwoSubsequences

    Type: Default 1000ms 256MiB

A.TwoSubsequences

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

A.TwoSubsequences

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 xy;

  • 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≤t≤1000). Description of the test cases follows. The first and only line of each test case contains one string s(2≤|s|≤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

3
fc
aaaa
thebrightboiler
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.

SWPU ROUND #4(DIV.3)

Not Attended
Status
Done
Rule
ACM/ICPC
Problem
6
Start at
2021-11-27 9:00
End at
2021-11-27 11:30
Duration
2.5 hour(s)
Host
Partic.
26