B. Least SigDig
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You're given two numbers $$$n$$$ and $$$m$$$, Your task is to calculate $$$n × 245^m$$$ and then print the least significant digit of it.

Input

The first line contains single integer $$$t$$$ the number of tests.

$$$1 \le t \le 10^3$$$.

Output

Each test contains two numbers, $$$n$$$ and $$$m$$$ respectively.

$$$0 \le n, m \le 10^9$$$.

Example
Input
3
1 1
2 1
2 2
Output
5
0
0
Note

For each test, print one integer in one line — the answer to the problem.