题目描述

小$K$坐曲率运动飞船来到了$\gamma$星，这里他发现$\gamma$星盛产一种奇特的珠子，用这种珠子串成的手链会产生一些奇特的效果，而样式不同的手链会产生不同效果。小$K$想知道有$t$种颜色的珠子串成一条由$N$个珠子组成的手链，一共有多少种不同的方案？

1、手链经旋转或翻转后若相同则算同一种方案。

2、手链必须由$N$颗珠子串成。

3、手链可由同一种颜色的珠子串成，且不同颜色的各算一种方案。

输入格式

第一行包含一个整数$k$。

第$2~k+1$行每行包含两个整数，分别代表手链所需珠子数量$N$和不同颜色的种类数$t$。

输出格式

输出一个整数代表方案数。

样例

样例输入

4
5 2
5 3
5 4
5 5

样例输出

8
39
136
377

数据范围与提示

对于 $30$ 的评测用例，$k \leq 100$, $1 \leq N \leq 20$，$t = 2$。

对于 $50$ 的评测用例，$k \leq 100$, $1 \leq N \leq 50$，$t \leq 3$。

对于所有评测用例，$k \leq 1000$, $1 \leq N \leq 50$，$2 \leq t \leq 10$。