求 1^b+2^b+\cdots + a^b 的和除以 10^4 的余数。
第一行一个整数 N，表示共有 N 组测试数据。对于每组数据，一行两个整数 a,b。
对于每组数据，一行一个整数，表示答案。
1 2 3
9
对于 30\% 的数据，N \le 10，a,b \le 10^3。对于 100\% 的数据，1 \le N \le 100，1 \le a,b \le 10^9。