Help Lazy Tareq

There is a boy named Tareq Abrar who is very lazy. He likes sleeping. He also likes eating. His mother is annoyed with him for his so much laziness. But she loves her son very much. This is why she can't punish him. She hit upon a plan. She gave Tareq a task to solve. She thought that Tareq would not remain lazy while solving the task. Tareq told his friend Issac Shimanto to solve this task. But Shimanto was busy with his newly married wife. Now, Tareq became sad finding no way for solving the task. Tareq knew that you are a famous programmer of the world. He wants your help solve the task. If you solve the task, Tareq Abrar will get opportunity to sleep again.

Tareq was given a positive integer which had a non-zero leading digit & all other digits were zero. He had to find the sum of all positive even divisors of this number.

You will be given the first digit of this number & the number of zeroes of this integer. You have to output the sum of all positive even divisors of this number.

The answer may be a big number. So, give output modulo $10000007$.

Input

There are several test cases. The first line of input contains a positive integer $T$ ($1 \le T \le 10^5$), which denotes the number of test cases.

In each line of next $T$ lines, there will be given two positive integers $N$ ($1 \le N \le 9$) and $X$ ($ 0 \le X \le 10^{17}$) separated by space. $N$ denotes the first digit of the number. $X$ denotes the number of zeroes.

Output

Output will contain $T$ lines. In each line, you have to print a non-negative integer which denotes the answer.

Sample

Input	Output
3 2 1 3 2 7 5	36 744 1937376
For the first one, the leading digit is 2, it has one 'zero'. So, it is 20. 2+4+10+20=36