输入描述:

第一行给定一个数t，表示有t组输入
接下来t行，每行给定两个数n,p；意义如题所示；
输入范围：(t<=1000)  (1<=n<=1000000 ） (2<=p<=1000000)

输出描述:

对于每一组输入，输出单独的一行表示答案。