SELFNUM  Fashionable selfdescribing numbers
Task
You decided to start an online dating site for mathematical objects. Every set, number, algebraic structure and lemma can register on your site and start describing its good qualities in its profile.
This is especially easy for numbers which directly describe themselves when you read them. For example, the number 10123133 contains one “0”, one “2”, three “1”s and three “3”s. We call numbers like that self describing numbers, and they are very popular.
A bit more formally, an integer is a selfdescribing number if we can split it into pairs of ((count, digit), (count, digit), (count, digit), …) where for every (count, digit) pair, our number really contains that digit that many times. All counts must be written without leading zeros and all digits appearing in the number must be specified exactly once.
However, the digit f has fallen out of fashion. Any number that contains the digit f has no chance.
Consider all selfdescribing numbers that don’t contain the forbidden digit f. Print the nth smallest such number. (The first n − 1 self describing numbers are out of your league.)
Input
The input contains multiple testcases. Their number 1 ≤ T ≤ 5 is on the first line.
Each testcase is a single line with two integers n and f, where 1 ≤ n ≤ 10^{9} and 0 ≤ f ≤ 9.
Output
Print the nth smallest self describing number that doesn’t contain the digit f.
The input will be chosen so that the answer always exists.
Examples
Input:
2
1 1
1 2
Output:
22
10143133
The number 22 is self describing – we can split it as ((2,2)). It is the smallest self describing number that doesn’t contain the digit 1.
We can read 10143133 as ((1, 0),(1, 4),(3, 1),(3, 3)). This is the smallest self describing number that doesn’t contain the digit 2.
hide comments
:D:
20191201 20:56:31
Wow, that was really great analysis heavy problem. Really enjoyed it, thanks Hodobox! Do you have any link to the problem you based this on?

Added by:  Hodobox 
Date:  20191127 
Time limit:  10s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  Modified from BIO 2019 