D. Polycarp and Div 3

 F1. Nearest Beautiful Number (easy version)

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

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

You are given an integer n$n$. Find the minimum integer x$x$ such that x≥n$x\ge n$ and the number x$x$ is k$k$-beautiful.

A number is called k$k$-beautiful if its decimal representation having no leading zeroes contains no more than k$k$ different digits. E.g. if k=2$k=2$, the numbers 3434443$3434443$, 55550$55550$, 777$777$ and 21$21$ are k$k$-beautiful whereas the numbers 120$120$, 445435$445435$ and 998244353$998244353$ are not.

Input

The first line contains one integer t$t$ (1≤t≤104$1\le t\le {10}^4$) — the number of test cases. Then t$t$ test cases follow.

Each test case consists of one line containing two integers n$n$ and k$k$ (1≤n≤109$1\le n\le {10}^9$, 1≤k≤2$1\le k\le 2$).

Output

For each test case output on a separate line x$x$ — the minimum k$k$-beautiful integer such that x≥n$x\ge n$.

Example

input

Copy

4
1 1
221 2
177890 2
998244353 1

output

Copy

1
221
181111
999999999