快樂數字 (Happy Number)
發布時間: July 4, 2020, 10:14 p.m. 最後更新時間: Sept. 15, 2023, 9:43 a.m. 時間限制: 1000ms 記憶體限制: 128M
小巴跟小華發明了一種新的遊戲，名字為「快樂數字」。這個遊戲的玩法如下，兩人遵照規則輪流說出一個符合條件的快樂數字，先說不出數字或數字重複的人就輸了，其規則如下：
$(1)$快樂數字不包含$0$。
$(2)$快樂數字須包含$1\sim 9$的每個數字。
$(3)$在快樂數字中，相鄰的位數數字之差至多為$2$。
給定快樂數字的位數以及其個位數字，請你寫一個程式計算符合此條件的快樂數字共有幾個，由於數字可能過大，因此請輸出個數除以$10^9+7$的餘數。
輸入第一行有一個正整數$N(1\leq N\leq 10^4)$，代表詢問數；緊接著共有$N$行，每行有兩個正整數$P(1\leq P\leq 10^3), Q(1\leq Q\leq 9)$，代表詢問以$Q$結尾的$P$位數快樂數字共有幾個。
對於每個詢問，請輸出快樂數字個數除以$10^9+7$的餘數。
複製範例
3 9 1 9 2 9 3
31 15 10
複製範例
2 12 5 14 7
27020 2273621
