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 <= i <= min(|a|, |b|) ) such that a_i < b_i , and for any index j ( 1 <= j < i ) a_j = b_j . Consider a sequence of strings s_1, s_2, ... , 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 + ... + s_n ( S is the concatenation of all strings s_1, s_2, ... , 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 <= t <= 10^4 ). Each test case consists of two lines. The first line contains the string s_1 ( 1 <= |s_1| <= 10^6 ), consisting of lowercase Latin letters. The second line contains the integer pos ( 1 <= pos <= 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.