You are given two integers, and . Count the number of strings of length (under the alphabet set of size ) that doesn't contain any palindromic string of the length greater than as a consecutive substring.
Input Format
Several test cases will be given to you in a single file. The first line of the input will contain a single integer, , the number of test cases.
Then there will be lines, each containing two space-separated integers, and , denoting a single test case. The meanings of and are described in the Problem Statement above.
Output Format
For each test case, output a single integer - the answer to the corresponding test case. This number can be huge, so output it modulo .
Constraints
Sample Input
2
2 2
2 3
Sample Output
2
6
Explanation
For the 1st testcase, we have an alphabet of size M = 2. For the sake of simplicity, let's consider the alphabet as [A, B]. We can construct four strings of size N = 2 using these letters.
AA
AB
BA
BB
Out of these, we have two strings, AB and BA, that satisfy the condition of not having a palindromic string of length greater than 1. Hence, the answer 2.
For the 2nd test case, we have an alphabet of size M = 3. For the sake of simplicity, let's consider the alphabet as [A, B, C]. We can construct nine strings of size N = 2 using these letters.
AA
AB
AC
BA
BB
BC
CA
CB
CC
Save AA, BB, and CC, all the strings satisfy the given condition; hence, the answer 6.