## MOZMCAN - Can Sharmeen Solve it? [ Medium ]

Somehow Sharmeen solved the last problem “**Sharmeen loves substring**” and Mozahid became impressed on her performance. Now Mozahid wants to test her programming skill and gives her the hardest problem of today’s problem set. He will give her a string of lowercase English letters of size N( 1 <= N <= 1000 ) and an integer X( 0 <= X <= 10^8 ). Sharmeen has to find the largest substring of that string, which has exactly X subsequences of ‘**sms**’. If multiple solution exists, she has to select the leftmost one. If no solution exist she has to print “-1” (without quotes); otherwise, she has to print the starting and ending position of the substring separated by a space in one line. For exact output format, see the Sample Input Output carefully.

**N.B.** Substring is a consecutive sequence of characters of a string, whereas subsequence does not necessarily need to be consecutive. But for both, you have to maintain the order. For clearance, ‘skmjssm’ has 2 different subsequence of ‘sms’. {1,3,5} & {1,3,6} ( 1 based position ).

### Input

In first line given test case T( 1 <= T <= 10 ).

For each test case, a string of lowercase English letters of size N( 1 <= N <= 1000 ) and an integer X( 0 <= X <= 10^8 ) are given, separated by a space.

### Output

For each test case, if solution exists print the starting and ending position of the substring ( 1 based position ) separated by a space, otherwise, print “-1” (without quote ) in one line .

### Example

Input:2

smsmmsms 1

mmsm 1Output:1 5

-1

[ This problem originally written by MD. Mozahidul Islam Bhuiyan(kissu_pari_na) ]

Added by: | Avik Sarkar |

Date: | 2018-06-22 |

Time limit: | 1s |

Source limit: | 50000B |

Memory limit: | 1536MB |

Cluster: | Cube (Intel G860) |

Languages: | All |

Resource: | Own |