Description

Robin found an interesting poneglyph, instead of being a readable text, it is encoded with a specific pattern.

To decode the text, Robin told Zoro to slice the string to split it into readable text with his sword.

If Zoro knew python, he could easily use str.split() function. But he's got no programming skills.

For those who are not familiar with how the split function works:

Take example, string = Ixyzamxyzluffy

string.split('xyz') will result into string == ['I', 'am', 'luffy']

 

Note: This is a partial judge problem, please implement the function.h and don't forget to compile with C compiler.

oh, and be careful of the memory usage allocated dynamically to avoid MLE.

 

Input

String S that should be splitted, 20 < S < 499

Pattern string P, 1 < P < 9

Output

Output the strings splited by the given pattern.

Don't forget to include '\n' at the end of each output string.

Sample Input  Download

Sample Output  Download

Partial Judge Code

14136.c

Partial Judge Header

14136.h

Discuss

Description

Let str be a string, we define a function f(str) as follows: the number of substrings of str where all characters in each substring are the same.

For example, f(s) = 5, where s='aabc'. The substrings where all characters are the same are: s[0,0]='a', s[1,1]='a', s[0,1]='aa', s[2,2]='b', and s[3,3]='c'.

Now, given a string s, you need to find a subsequence s' of s such that f(s') is maximized. A subsequence of a string is formed by deleting some characters from the string without changing the order of the remaining characters. For example, "chy" and "cye" are subsequences of "chyen", but "cey" is not.

 

Input

The first line of the input is an integer T, denoting the number of testcases. 1<= T <= 10

Next T lines indicate T strings s to find such subsequence.

1 <= length of s <= 20

Note that s only contains lowercase English alphabets.

Output

For each testcase, let s' be the subsequence of s that maximize f(s'). Output f(s').

Remember to output '\n' at the end of each line.

 

Hint

In the sample testcase 1, s'='aaa'. In the sample testcase 2, s'='abbb'.

Sample Input  Download

Sample Output  Download

Discuss