SP8410 SNAKYNUM - Snaky Numbers

Sanky 是一个爱好数字的小学生。他的老师布置了一项家庭作业，要求班里每位同学都要发明一个新数列，其中要包含大量的数字。他的朋友 Evan 发明了一个数列，这个数列从 0 开始，每隔一个数选择一个数字，即 {0, 2, 4, ...}，并命名为“Evan 数”。Sanky 因为没能第一个发明这个数列而感到不快，并认为从 1 开始每隔一个数选择的数列 {1, 3, 5, ...} 也没什么特别的。 回到家后，Sanky 想出了一个新的数列，其中数字呈现出一种锯齿形规律的排列方式，也就是说，数字的各位交替地比前一位数字增加或减少。具体地说，如果这个数字是 abcde，那么要么是 a < b > c < d > e，要么是 a > b < c > d < e。这种数列被他称为“Snaky 数”。例如，8、90、243516 和 31524 是 Snaky 数，而 44、123 和 4235 则不是。现在，Sanky 想知道他的 Snaky 数列是否足够庞大。他特别想知道，不超过给定长度 $N$ 的“Snaky 数”一共有多少个。我们只考虑非负整数，且不允许有前导零。 答案可能会非常大，以至于无法写在 Sanky 的作业本上，所以请计算出结果并返回答案模 $M$ 的值。

第一行输入一个整数 $T$，表示测试用例的数量（大约 50 个）。接下来的 $T$ 行中，每行包含两个整数 $N$ 和 $M$。 $1 \leq N \leq 1,000,000,000$ $2 \leq M \leq 1,000,000,007$

对于每个测试用例，请在单独的一行中输出 (长度不超过 $N$ 的 Snaky 数的数量) % $M$。 **本翻译由 AI 自动生成**