Migrated from Lutece 1976 主楼

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

电孑科技大学清水河主楼之中隐藏着一座扭曲时空的迷阵，未曾掌握时空魔法的人一旦进入其中就会被其拘束不能复出。

你，一名勇敢的探险者，确信自己已经陷入了迷阵，并且发现这个迷阵有一定的规律，总是在行进一定距离之后回到最初的起点，继续往前走会踏上重复的道路，再次遇到重复的 NPC 。

为了分析这个迷阵的布局，你在主楼中记录下了一些前进中遇到的标记，你现在想知道，从起点开始，最少行进多少距离之后可能会回到初始状态？

说人话：给定字符串S，求最短循环节T，使得S是TTT....T（无数个T）的子串

Input

输入文件中第一行一个小于 100 的正整数 $T$ 表示测试数据组数。

第一行有一个正整数 $n$ 为字符串长度， $1\le n\le10^5$

第二行长为 $n$ 的字符串，仅包含 a-z 的小写英文字母非空字符串。

Output

对于每组测试数据：

第一行输出从起点再次回到起点的行进距离，

第二行输出行进路上遇到的字符。

Samples

2
4
abcd
7
abaabaa

4
abcd
3
aba

Note

Resources

2018 UESTC ACM Training for Search Algorithm and String