CF1886C.Decreasing String

Recall that string $a$ is lexicographically smaller than string $b$ if $a$ is a prefix of $b$ (and $a \ne b$ ), or there exists an index $i$ ( $1 \le i \le \min(|a|, |b|)$ ) such that $a_i < b_i$ , and for any index $j$ ( $1 \le j < i$ ) $a_j = b_j$ .

Consider a sequence of strings $s_1, s_2, \dots, s_n$ , each consisting of lowercase Latin letters. String $s_1$ is given explicitly, and all other strings are generated according to the following rule: to obtain the string $s_i$ , a character is removed from string $s_{i-1}$ in such a way that string $s_i$ is lexicographically minimal.

For example, if $s_1 = \mathrm{dacb}$ , then string $s_2 = \mathrm{acb}$ , string $s_3 = \mathrm{ab}$ , string $s_4 = \mathrm{a}$ .

After that, we obtain the string $S = s_1 + s_2 + \dots + s_n$ ( $S$ is the concatenation of all strings $s_1, s_2, \dots, s_n$ ).

You need to output the character in position $pos$ of the string $S$ (i. e. the character $S_{pos}$ ).

The first line contains one integer $t$ — the number of test cases ( $1 \le t \le 10^4$ ).

Each test case consists of two lines. The first line contains the string $s_1$ ( $1 \le |s_1| \le 10^6$ ), consisting of lowercase Latin letters. The second line contains the integer $pos$ ( $1 \le pos \le \frac{|s_1| \cdot (|s_1| +1)}{2}$ ). You may assume that $n$ is equal to the length of the given string ( $n = |s_1|$ ).

Additional constraint on the input: the sum of $|s_1|$ over all test cases does not exceed $10^6$ .

For each test case, print the answer — the character that is at position $pos$ in string $S$ . Note that the answers between different test cases are not separated by spaces or line breaks.