Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Sum of Digits

time limit per test

2 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputLet $$$f(x)$$$ be the sum of digits of a decimal number $$$x$$$.

Find the smallest non-negative integer $$$x$$$ such that $$$f(x) + f(x + 1) + \dots + f(x + k) = n$$$.

Input

The first line contains one integer $$$t$$$ ($$$1 \le t \le 150$$$) — the number of test cases.

Each test case consists of one line containing two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 150$$$, $$$0 \le k \le 9$$$).

Output

For each test case, print one integer without leading zeroes. If there is no such $$$x$$$ that $$$f(x) + f(x + 1) + \dots + f(x + k) = n$$$, print $$$-1$$$; otherwise, print the minimum $$$x$$$ meeting that constraint.

Example

Input

7 1 0 1 1 42 7 13 7 99 1 99 0 99 2

Output

1 0 4 -1 599998 99999999999 7997

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/22/2021 07:38:09 (k2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|