题目说明

我们每个人应该都听过牛郎和织女的传说，但是你们知道吗？牛郎的真名其实叫做————茶山牛

经过茶山牛不懈的努力，王母娘娘终于同意了让他跟织女见上一面，但是必须得解决王母娘娘的一个问题。

王母娘娘给出两个数字 $n,m$ ，要求茶山牛在1s内回答出 $(n!!!)$ % $m$ 的值（即 $n$ 的阶乘的阶乘的阶乘对 $m$ 取模后的值），这可真是难为茶山牛了，毕竟一心只想见到织女，所以你能帮助他解决这个问题吗？

输入描述:

多组输入，第一行一个正整数 $t ( 1 \le t \le 10^{5} )$ 表示数据组数 每组数据包含两个整数 $n,m( 0 \le n \le 10^{9},1 \le m \le 10^{9} )$

输出描述:

对于每组输入，输出一个整数，代表答案。

用例

输入

2
2 6553
2 2

输出

2
0