生日礼物的意外

Time Limit: 3000 ms

Memory Limit: 65535 ms

Description

我们的大队长xiaoyoulei同学,在过生日的时候收到了rayafjyblue送他的手链,这个手链是什么样子的呢,它有n个珠子,这n个珠子颜色都是不一样的,但是不小心被bobo弄散了,xiaoyoulei很生气,结果把波波揍了一顿,并且从此以后就很低落,bobo看见他那么低落,心里很难过,于是bobo准备自己买n个无色的珠子,并且买了n中染料,准备图成原来的样子,送给xiaoyoulei,但是悲剧的是,他不知道原来的手链是什么颜色。由于他的人品比较尴尬,所以他想知道,到底有多少不同的方案。我们认为经过旋转以后变成一样的是同一种,由于bobo眼神很好,所以他可以保证他每次不会接成一样的方案,现在他很头疼,所以他来问我,但是由于我要出题,所以我就问你们了

Input

第一行有一个整数M,表示测试数据的个数
以下M行:一个整数n,表示有多少个珠子,n<=1000000;一个整数p,表示模除的整数,p=30000

Output

输出一个整数,表示最多尝试的次数,由于数字会很大,所以最后的值模除一个30000

Sample Input

4
1 30000
2 30000
3 30000
4 30000

Sample Output

1
3
11
70

Hint

请使用long long,不要使用__int64

Source

watermelon::hdd

提交代码