变种汉诺塔问题和普通汉诺塔问题略有不同，规则描述如下：

1. 有三根柱子，在最左侧柱子上放置着若干圆盘。与传统汉诺塔不同的是，其中存在部分大小相同的圆盘。
2. 要求包括初始状态在内，每个圆盘上方放置的圆盘不得大于该圆盘，即圆盘上方只能放置小于自己或和自己相同大小的圆盘。
3. 每次移动只能将某柱子最顶部的一个圆盘移动到另一柱子的最顶部。
4. 需要注意的是，大小相同的圆盘具有的其他特征是不一样的，例如不同颜色。
   最后需要保证2号柱子上的圆盘排列顺序，和开始时的0号柱子上的顺序完全相同。
   求将初态0号柱子上的所有圆盘全部移到2号柱子上最优策略的步数 $l$对 $m$ 取模后的值。

第一行有一个整数 $t\ (1 \le t \le 100)$，表示有 $t$ 组数据。
对于每组数据：
第一行包括2个数字 $n,m\ (1\le n\le 15000,1\le m\le 1000000)$，其中 $n$ 代表圆盘种类的个数；
第二行包括 $n$ 个数字 $a_1,…,a_n\ (1\le a_i\le 99)$，其中 $a_i$ 代表大小为 $i$ 的圆盘个数。

对于每组数据，输出一行，若最优策略的步数为 $l$，则输出 $l\ \text{mod}\ m$。