游客 Signup | Login
中文 | En

2647 - 子串

通过次数

0

提交次数

0

Time Limit : 1 秒 Memory Limit : 128 MB

给你一个字符串S,只包含小写字母,你需要按字典序输出它的所有不同子串。

Input

第一行一个整数t,表示数据量。

每组数据包含一个字符串S。

1<= t<= 5;

1<= strlen(S)<= 600;


Output

输出如题。

Examples

Input Format

2
abc
cba

Output Format

a
ab
abc
b
bc
c
a
b
ba
c
cb
cba