Acesrc is a famous mathematician at Nanjing University second to none. Playing with interesting numbers is his favorite. Today, he finds a manuscript when cleaning his room, which reads
... Let f(d,n)f(d,n) denote the number of occurrences of digit dd in decimal representations of integers 1,2,3,⋯,n1,2,3,⋯,n. The function has some fantastic properties ...
... Obviously, there exist some nonnegative integers kk, such that f(d,k)=kf(d,k)=k, and I decide to call them dd-good numbers ...
... I have found all dd-good numbers not exceeding 101000101000, but the paper is too small to write all these numbers ...
Acesrc quickly recollects all dd-good numbers he found, and he tells Redsun a question about dd-good numbers: what is the maximum dd-good number no greater than xx? However, Redsun is not good at mathematics, so he wants you to help him solve this problem.
Input
The first line of input consists of a single integer qq(1≤q≤1500)(1≤q≤1500), denoting the number of test cases. Each test case is a single line of two integers dd(1≤d≤9)(1≤d≤9) and xx(0≤x≤1018)(0≤x≤1018).
Output
For each test case, print the answer as a single integer in one line. Note that 00 is trivially a dd-good number for arbitrary dd.