Description

Find the remainder when the sum $1^b+2^b+\cdots + a^b$ is divided by $10^4$.

Input Format

This problem contains multiple test cases.

The first line contains an integer $N$, indicating that there are $N$ test cases.

For each test case, one line contains two integers $a,b$.

Output Format

For each test case, output one integer per line, the answer.

1
2 3

9

Hint

For 30% of the testdata, $N \le 10$, $a,b \le 10^3$.

For 100% of the testdata, $1 \le N \le 100$, $1 \le a,b \le 10^9$.

Translated by ChatGPT 5