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. It's 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