SP3359 STACK - Stack

Alan特别喜欢搭建积木堆。他的积木堆中有很多正方形底的立方体，并且所有立方体的高都是1.Alan把连续的立方体堆起来放。 最近Alan在数学课上学到了体积这个概念，因此他想算出积木堆的体积。Alan是这么构造立方体底（从上端到下端）的长度的： - 第一个正方形边缘长度为1（a(1)=1）; - 然后构造第二个长方形的边缘长度a(2); - 接下来Alan会计算an的长度（n>2）,也就是2* a(2) * a(n-1)-a(n-2).(别问我为什么他会用这样一个公式。。。就当他是个特别奇特的小伙子吧)

输入中有很多个case。 第一行是case的数量t(t

计算出每一个case中Alan造出的N个连续的立方体的体积（根据规则1-3），结果按m取模输出。