SP20635 DORTMUND - Dortmund Dilemma

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_**.

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_**.

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