题目描述

求 $1^b+2^b+\cdots +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$。