Migrated from Lutece 1167 一句话题意

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

请问从n*n的正方形左下角走到右上角且不越过对角线的情况总数模m的结果~

Input

第一行为一个整数t(0<t<=100),表示数据组数。下面接着t行，每行两个数n,m(1<n<10^9,2<m<10^5)。m是质数。

Output

对于每组数据，输出答案模m的结果。如果对题意不是很清楚请看hint。

Samples

2
2 5
4 3

2
2

Note

这是4*4的情况，一共有14种情况

Resources

2015 UESTC ACM Training for Math