Umang wants to know the password of web kiosk of his best friend, he has a string with him which contains the password. The Password is a substring of s such that it is proper prefix as well as the proper suffix of the string of maximum length(proper prefix and proper suffix can be overlapping also) .

Help Umang in identifying the Password and no of times it appears in the string.

Proper Prefix is the prefix which is not equal to whole string itself, same goes for a proper suffix.

Note: prefix and suffix may overlap.

Input Format:

First line contains no of test case

Each of the next line contains an string where each character of the string is lowercase english alphabet.

Output Format:

In first line print the password and in next line print it's frequency.

if there is no password in the string then print -1.

Constraints:

1<= T <=10

1<= length of string <= 3*10^5 

Problem Author :

Adish Agarwal