题目背景

今天，新高一的OIer们第一次进入了机房。z老师想让他们喜欢上OI，于是给了他们每个人一个三角形。 这时候，小q秃发奇想，拿着手中的三角形，给大家出了一道题，请你帮助他们给小q一个正确的答案。

题目描述

小q给了你两个整数n,m ，请输出杨辉三角前 n行的所有数的和模 m的值。 如果你不知道杨辉三角是什么，请看样例解释。

输入格式

每个测试点有多组测试数据。 每个测试点第一行一个正整数T表示数据组数。 接下来 行每行两个正整数 n,m 表示一次询问。

输出格式

共T行，每行一个正整数，表示答案。

样例 #1

样例输入 #1

3
5 6
7 2
2 998244353

样例输出 #1

3 
3
1

提示

样例解释 杨辉三角如下： 第一行： 1 第二行： 1 1 第三行： 1 2 1 第四行： 1 3 3 1 第五行： 1 4 6 4 1 第六行： 1 5 10 10 5 1 这个三角的生成方式如下：

1. 第i 行（ 是正整数）有i 个数。
2. 记第i 行从左到右数第j 个数为aij （i,j 都是正整数），则

可见前6行的和为63 ,对 5取模后结果为3 。 前2行的和为3 ,对 7取模后结果为3 。 说明/提示 对于10% 的数据，满足n<=5 ； 对于 20% 的数据，满足 T=1,n<=50 ； 对于40% 的数据，满足T<=10,n<=100 ； 对于 60% 的数据，满足n<=106 ； 对于 90%的数据，满足n<=1018 ； 对于100% 的数据，满足T<=103 ，m<=1018, n<=101000保证 m为质数。