Anti-Palindromic Strings

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 1^st 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 2^nd 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.