Напомним, что строка $$$a$$$ лексикографически меньше строки $$$b$$$, если $$$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$$$. Обратите внимание, что ответы между разными наборами входных данных не разделяются ни пробелом, ни переводом строки.
3cab6abcd9x1
abx
