SP21683 BGTSTR - Bhagat and String

``` 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

N/A

N/A