Cuber Occurrence

Recently, Cuber QQ has received a letter from his old friend Little Fang, which is a strangely long paper note. Cuber QQ thought it will be interesting to count the occurrences of some words in this paper note, thus he brought in a dictionary. If you are curious about what occurrences mean, here are some examples: "nan" appears once in "banana"; "a" appears 3 times in "banana", "ana" appears twice in "banana".

When Cuber QQ got up the second day, he forgot all about his counting yesterday, and he figured he had to do that again. So he used a highlight pen and highlighted those occurrences. Note that a letter can't be highlighted more than once. For example, finding "ana" in "banana" will result in highlighting altogether 5 letters.

On the third day, Cuber QQ again noticed a problem he could have noticed on the second day. He can't tell the number of occurrences from his highlighting because of some touching or overlapping area. If you are counting "a" in "banana", you will get 3; that's fine. Counting "an" or "ana" will all give you the wrong count, which is 1. Cuber QQ has finally given up and named his incorrect counting as Cuber Occurrence.

Let's do a more complicated example to make sure everything is clear. Cuber Occurrence of "cuc" in "cucucuberqqcucuber" is 2, and that of "q" is 1 (since two "q" are touching each other), and that of "u" is 5.

Cuber QQ couldn't help wondering the opposite problem. If he knows the Cuber Occurrence of a word in a string, could you find him this word?

The first line of the input contains an integer $t$ ($1 \le t \le 100$), indicating there are $t$ tests.

The follows $t$ test cases, Each test consists of two lines. The first line contains a lowercase ascii string $s$ ($1 \le |s| \le 10^5$ , $\sum |s|\le 10^6$), and the second line is an integer $k$ ($1 \le k \le |s|$).

For each test case, output a word in one line, which has the Cuber Occurrence of $k$ in $s$. In case there are more than one solutions, output the lexicographically smallest one. If there is no such string, output $-1$ instead.

4
cucucuberqqcucuber
2
cucucuberqqcucuber
5
cucucuberqqcucuber
1
cucucuberqqcucuber
10

b
c
berq
-1

Special note if you are doing this problem on HDOJ: The memory limit can be a little tight as 512MB is the best we can do.

2019 Multi-University Training Contest 7