String Game 2

Interview

Time limit1sMemory limit1024 MB

Summary

For each test case, find the shortest substring containing exactly K of some character, and the longest substring that both starts and ends with that character and contains exactly K of it.

Level: Medium6 of 10
Topics: String, Sliding window, Two pointers, Implementation
Solved: No attempts yet

Problem

Following last year, there is a new string game. The game proceeds as follows.

A string W consisting of lowercase alphabet letters is given.
A positive integer K is given.
Find the length of the shortest contiguous substring that contains exactly K occurrences of some character.
Find the length of the longest contiguous substring that contains exactly K occurrences of some character and whose first and last characters are both that character.

The game is played T times in this way.

Input

The number of string games T is given. (1 ≤ T ≤ 100)

From the next line, over 2 lines, a string W and an integer K are given. (1 ≤ K ≤ |W| ≤ 10,000)

Output

For T lines, print the lengths of the contiguous substrings obtained in steps 3 and 4 of the string game, separated by a space.

If no such contiguous substring exists, print -1.

Examples2

Example 1

Input

2
superaquatornado
2
abcdefghijklmnopqrstuvwxyz
5

Expected output

4 8
-1

Example 2
Input
```
1
abaaaba
3
```
Expected output
```
3 4
```