A. Yet Another Short Statement
time limit per test
1 с
memory limit per test
256 megabytes
input
standard input
output
standard output

Given four positive integers $$$l$$$, $$$r$$$, $$$k$$$, and $$$x$$$, we want to find the $$$k^{\text{th}}$$$ smallest positive integer in the range from $$$l$$$ to $$$r$$$ inclusive, which has a digit sum of exactly $$$x$$$.

Input

First line of the input contains a single integer $$$t(1 \le t \le 10^5)$$$ — number of test cases.

Each test case contains four integers $$$l, r, k, x$$$ $$$(1 \le l \le r\le 10^{18}, 1 \le k, x \le 10^{18})$$$.

Output

For each test case, print the answer, asked in the statement, if there are at least $$$k$$$ numbers that have digit sum of exactly $$$x$$$ in the range from $$$l$$$ to $$$r$$$. Print $$$-1$$$ otherwise.

Example
Input
6
1 10 1 1
1 10 2 1
1 10 3 1
1 100 3 1
2 10000000 10 5
546445 10000000 10 5
Output
1
10
-1
100
131
1000202