描述

$N$ 种颜色的珠子连接在一起，形成一条由 $N$ 颗珠子组成的圆形项链 （$N \leq 10^{10}$）。你的工作是计算可以生产多少种不同种类的项链。你应该知道，项链可能不会用完所有 $N$ 种颜色，并且围绕圆形项链中心旋转产生的重复都被忽略了。

你只需向答案模块输出给定的数字 $P$。

输入

输入的第一行是一个整数 $X$ （$X \leq 3500$），表示测试用例的数量。以下 $X$ 行分别包含两个数字 $N$ 和 $P$ （$1 \leq N \leq 10^{10}$，$1 \leq P \leq 30000$），表示一个测试用例。

输出

对于每个测试用例，输出一行包含答案。

输入数据 1

5
1 30000
2 30000
3 30000
4 30000
5 30000

输出数据 1

1
3
11
70
629

来源

$POJ 月刊，娄天成$