Bhagat loves string very much. Bhagat is given a string S and an integer N. He hates a string Pwhich is substring of S and occurs atleast N times in S. Your task is to find maximum length of substring P of S which occurs at least N times.
If there are multiple solution then substring with right most occurence is preferred. 
S consist of only lowercase letters.

INPUT
First line will contain T , denoting number of test cases
Each test case consist of two line
First line contain the string S
Next line contain an integer N
OUTPUT
If there is no solution, output HATE,otherwise, print two integers in a line, separated by a space. The first integer denotes the maximum length of a substring appearing at least N times; the second integer gives the rightmost possible starting position of such a substring.
CONSTRAINS
0 < T <= 10
1 <= |S| <= 50000
1 <= N <= |S|
SAMPLE INPUT
3
aaaaaaa
3
babab
2
abcde
3

SAMPLE OUTPUT
5 3
3 3
HATE