时间限制：1秒　　内存限制：256M

---

【问题描述】

　　计算　\((1^b+2^b+⋯+a^b )\ mod\ 10000\) 的值。

【输入格式】

　　第一行一个整数 \(T\)，表示有 \(T\) 组测试数据；
　　接下来 \(N\) 行，每行包含两个正整数 \(a\) 和 \(b\) 。

【输出格式】

　　\(n\) 行，对应输入的答案。

【输入输出样例1】

　Input

3
2 3
7 23
233302333 3220322

　Output

9
2384
8079

【数据限制】

　　30% 的数据满足：\(1 ≤ T ≤ 10 ，0 < a,b ≤ 1000\)
　　100% 的数据满足：\(1 ≤ T ≤ 100 ，0< a,b ≤ 1000000000\)

【来源】

　ITer