【cfgym100541】Treasure Box

2015年3月14日1,1560

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 Xdescribed as follows:

X = X + Xmod 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.

Sample test(s)
input

output

 

题解

x转换y次的增加值和x%100转换y次相同

预处理0-99转换1-50000次的答案

就能每50000一次转移了。。。

或者倍增也可以