D. Treasure Box
time limit per test
2 seconds
memory limit per test
256 megabytes
input
stdin
output
stdout

Your team was exploring an ancient city. Suddenly you found an old scroll with 2 integer numbers N and K, which encrypts the secret code to open a treasure box. Considering a transformation on an integer X described as follows:

X = X + X mod 100,

the secret code can be obtained by applying the above-described transformation K times successively to N.

Input

The input file consists of several datasets. The first line of the input file contains the number of datasets which is a positive integer and is not greater than 500.

Each dataset has two space-separated positive integers N and K (1 ≤ N ≤ 109, 1 ≤ K ≤ 109) written on a single line.

Output

For each dataset, write on a single line the secret number decrypted from N and K.

Examples
Input
2
31102014 2
10101 10
Output
31102056
10324