#P1560F1. Nearest Beautiful Number (easy version)

    ID: 1906 Type: RemoteJudge 1000ms 256MiB Tried: 0 Accepted: 0 Difficulty: 6 Uploaded By: Tags>binary searchbitmasksbrute forceconstructive algorithmsdfs and similargreedy*1900

Nearest Beautiful Number (easy version)

Description

It is a simplified version of problem F2. The difference between them is the constraints (F1: k2k \le 2, F2: k10k \le 10).

You are given an integer nn. Find the minimum integer xx such that xnx \ge n and the number xx is kk-beautiful.

A number is called kk-beautiful if its decimal representation having no leading zeroes contains no more than kk different digits. E.g. if k=2k = 2, the numbers 34344433434443, 5555055550, 777777 and 2121 are kk-beautiful whereas the numbers 120120, 445435445435 and 998244353998244353 are not.

The first line contains one integer tt (1t1041 \le t \le 10^4) — the number of test cases. Then tt test cases follow.

Each test case consists of one line containing two integers nn and kk (1n1091 \le n \le 10^9, 1k21 \le k \le 2).

For each test case output on a separate line xx — the minimum kk-beautiful integer such that xnx \ge n.

Input

The first line contains one integer tt (1t1041 \le t \le 10^4) — the number of test cases. Then tt test cases follow.

Each test case consists of one line containing two integers nn and kk (1n1091 \le n \le 10^9, 1k21 \le k \le 2).

Output

For each test case output on a separate line xx — the minimum kk-beautiful integer such that xnx \ge n.

Sample Input 1

4
1 1
221 2
177890 2
998244353 1

Sample Output 1

1
221
181111
999999999