求和
题目描述
求 $1^b+2^b+\cdots + a^b$ 的和除以 $10^4$ 的余数。
输入输出格式
输入格式
**本题有多组数据。**
第一行一个整数 $N$,表示共有 $N$ 组测试数据。
对于每组数据,一行两个整数 $a,b$。
输出格式
对于每组数据,一行一个整数,表示答案。
输入输出样例
输入样例 #1
1
2 3
输出样例 #1
9
说明
对于 $30\%$ 的数据,$N \le 10$,$a,b \le 10^3$。
对于 $100\%$ 的数据,$1 \le N \le 100$,$1 \le a,b \le 10^9$。