回想一下,如果 $$$a$$$ 是 $$$b$$$ 的前缀(并且 $$$a \ne b$$$),或者存在索引 $$$i$$$ ($$$1 \le i \le \min(|a|, |b|)$$$),使得 $$$a_i < b_i$$$,并且对于任何索引 $$$j$$$ ($$$1 \le j < i$$$) $$$a_j = b_j$$$。
考虑一系列字符串 $$$s_1, s_2, \dots, s_n$$$,每个字符串都由小写拉丁字母组成。字符串 $$$s_1$$$ 是显式给出的,所有其他字符串都根据以下规则生成:要获得字符串 $$$s_i$$$,请从字符串 $$$s_{i-1}$$$ 中删除一个字符,以使字符串 $$$s_i$$$ 在字典顺序上最小。
例如,如果 $$$s_1 = \mathrm{dacb}$$$,则字符串 $$$s_2 = \mathrm{acb}$$$、字符串 $$$s_3 = \mathrm{ab}$$$、字符串 $$$s_4 = \mathrm{a}$$$。
之后,我们得到字符串 $$$S = s_1 + s_2 + \dots + s_n$$$ ($$$S$$$ 是所有字符串 $$$s_1, s_2, \dots, s_n$$$ 的串联)。
需要输出字符串$$$S$$$中位置$$$pos$$$的字符(即字符$$$S_{pos}$$$)。
输入
第一行包含一个整数 $$$t$$$ — 测试用例的数量 ($$$1 \le t \le 10^4$$$)。
每个测试用例由两行组成。第一行包含字符串 $$$s_1$$$ ($$$1 \le |s_1| \le 10^6$$$),由小写拉丁字母组成。第二行包含整数 $$$pos$$$ ($$$1 \le pos \le \frac{|s_1| \cdot (|s_1| +1)}{2}$$$)。您可以假设 $$$n$$$ 等于给定字符串的长度 ($$$n = |s_1|$$$)。
对输入的附加约束:所有测试用例的 $$$|s_1|$$$ 总和不超过 $$$10^6$$$。
输出
对于每个测试用例,打印答案 - 字符串 $$$S$$$ 中位于 $$$pos$$$ 位置的字符。请注意,不同测试用例之间的答案不以空格或换行符分隔。
示例
输入 #1
3 cab 6 abcd 9 x 1
输出 #1
abx