Cornelia Street

“We bless the rain on Cornelia Street, memorize the creaks in the floor.”

Creak,creak,creak...The drum beats regularly.To keep the number of syllables in harmony, one sentence in chorus is as long as one in verse. However, drumbeats in the chorus is much stronger.

Jessica wants to memorize the music, piano and drumbeat. She records the music and encodes it into a string. So, the recorded string is so strange.

Let A be the pattern of verse and B be the pattern of chorus. So A $\neq$ B and |A| = |B|. The recorded string S is in the pattern of AAA$\cdots$A BB$\cdots$B AAAAA$\cdots$Aa. Formally, it is formed as n times repeat of A, m times repeat of B, k times repeat of A, and the broken piece a at the end is one prefix of A. And note that n,m,k > 0,|a|≥ 0.

Now Jessica wants to know the pattern of A and B. Can you help her?

The first line contains a number T (1 ≤ T ≤ 10) denoting the count of testcases.

For each testcase,one line containing a string S (7 ≤|S|≤ $8\times 10^5$).Note that S consists of only lowercase letters and uppercase letters.

It is guaranteed that $\sum$|S| ≤ $4.5\times 10^6$. The patterns in all testcases are generated randomly, but the character sets are different. There are 30% testcases generated in full character set, and the rest 70% are generated in large number of single character and small number of other characters.

For each testcase,output one line containing string A and B respectively,separated by one space.If there are multiple answers, choose the shortest one.

3
aaaaaaaaaabaabaaaaaa
ABABABABZXCVZXCVABABABA
abcababcacabcacabcababc

aaa aba
ABAB ZXCV
abcab abcac

“红旗杯”第十五届黑龙江省大学生程序设计竞赛