BGTSTR - Bhagat and String

no tags 

Bhagat loves string very much. Bhagat is given a string S and an integer N. He hates a string P which is substring of S and occurs at least 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 solutions then substring with right most occurrence is preferred.

Input

First line will contain T, denoting number of test cases. Each test case consist of two lines. The first line contains the string S and the next line contains the 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.

Constraints

0 < T <= 10

1 <= |S| <= 50000

1 <= N <= |S|

S consists of only lowercase letters.

Sample

Input:
3
aaaaaaa
3
babab
2
abcde
3

Output:
5 3
3 3
HATE

hide comments
(Tjandra Satria Gunawan)(曾毅昆): 2015-01-14 05:39:30

be careful when N=1, it cost me 1 WA.
Nice problem by the way :-)


Added by:NISHANT RAJ
Date:2014-11-05
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64