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