一场考试怎么能没有大模拟呢qwq，SKY_magician听说过猪国杀、德州扑克、UNO、杀蚂蚁等等，但是他觉得这些模拟写起来太短了，于是他就设计了一个肯定不会超过1500行的大模拟（划掉）。
现在你有一个4*n的棋盘和一坨地斗主骨牌，这些骨牌都是1*2的。请你求出用骨牌完全覆盖这个棋盘的方案数对m取模的值。
第一行一个T表示数据组数
对于每组数据输入n和m，n和m意义见题目描述。
输出答案
对于10%的数据 1<=n<=6
对于50%的数据 1<=n<=10000
对于70%的数据 1<=n<=5e7
对于100%的数据 1<=n<=1e9，1<=m<=1e5，T<=1500