Color
题号：NC232530
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

n个珠子组成的项链，用n种颜色染色，能够组成多少种不同的项链。（旋转后相同算同一种项链）
答案可能很大，请输出后的结果。

输入描述:

第一行包含一个整数，表示T组数据。
接下来T行，每一行包含两个整数。

输出描述:

输出T行，每一行输出一个整数表示答案。
示例1

输入

复制 
5
1 30000
2 30000
3 30000
4 30000
5 30000

输出

复制 
1
3
11
70
629

备注:

原题链接：http://poj.org/problem?id=2154