P1630 Summation

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

**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$.

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

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