Borussia Dortmund is a famous football (soccer) club from Germany. Apart from their fast style of playing, the thing that makes them unique is the hard to pronounce names of their players (Błaszczykowski, Papastathopoulos, Großkreutz etc.).

The team's coach is your friend. He is in a dilemma as he can't decide how to make it easier to call the players by name, during practice sessions. So, you advised him to assign easy names to his players. A name is easy to him if

1. It consists of only lowercase English letters.
2. Its length is exactly N.
3. It contains exactly K different letters from the 26 letters of English alphabet.
4. At least one of its proper prefixes matches with its proper suffix of same length.

Given, N and K you have to tell him the number of easy names he can choose from modulo (10^9+9).

Note : A prefix P of a name W is proper if, P ≠ W. Similarly, a suffix S of a name W is proper if, S ≠ W.

Input

The first line of the input will contain T ( the number of testcases ).
Each of the next T lines will contain two space separated integers N and K.

Output

For each testcase, output the number of ways the coach can assign names to his players modulo (10^9+9).

Constraints

1 ≤ T ≤ 10⁵ 
1 ≤ N ≤ 10⁵   
1 ≤ K ≤ 26

Example

Input:
8
1 1
2 1
4 2
2 2
5 1
3 2
6 2
1 3
Output:
0
26
2600
0
26
650
13650
0