SELFNUM - Fashionable self-describing 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 one0”, one2”, three1”s and three3”s. We call numbers like that self describing numbers, and they are very popular.

A bit more formally, an integer is a self-describing 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 self-describing numbers that don’t contain the forbidden digit f. Print the n-th 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 ≤ 109 and 0 ≤ f ≤ 9.

Output

Print the n-th 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.


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

hide comments
2019-12-01 20:56:31 :D
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?

RE: The problem is 'Allusional Almanac' from https://www.olympiad.org.uk/papers/2019/final/round_two.html

Last edit: 2019-12-02 02:07:08
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.