说明

求 $1^b +2^b +⋯+a^b$   的和除以 $10^4$ 的余数。

输入格式

第一行一个整数 N，表示共有 N 组测试数据。 

对于每组数据，一行两个整数 a,b。

输出格式

对于每组数据，一行一个整数，表示答案。

样例

1
2 3

9

提示

对于 30% 的数据， $N≤10$， $a,b≤10^3$。 

对于 100% 的数据， $1≤N≤100$， $1≤a,b≤10^9$。