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 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 ≤ 10⁹ 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.