SP20635 DORTMUND - Dortmund Dilemma

多特蒙德是德国的一支著名足球俱乐部。除了他们快速的踢球风格，球员名字难以发音也是他们的标志性特点（如 błaszczykowski、papastathopoulos、großkreutz 等）。 你的朋友是球队的教练，他在训练中使用球员名字时遇到了困扰。为了帮助他简化称呼，你建议给球员们分配一些简单的名字。一个名字对他来说算是简单的，需满足以下条件： 1. 仅包含小写英文字母。 2. 名字长度正好为 **_N_**。 3. 包含的不同字母恰好有 **_K_** 个，这些字母来自英文字母表中的 **_26_** 个字母。 4. 至少有一个**真前缀**与一个**真后缀**匹配，且长度相同。 面对给定的 **_N_** 和 **_K_**，你需要计算出教练可以选择的简单名字数，并将结果对 **_(10^9+9)_** 取模。 **注：** 如果名字 **_W_** 的前缀 **_P_** 满足 **_P_ ≠ _W_**，那么 **_P_** 是一个真前缀。同样地，后缀 **_S_** 如果满足 **_S_ ≠ _W_**，则 **_S_** 是一个真后缀。

第一行输入一个整数 **_T_**，表示测试用例的数量。 接下来的 **_T_** 行中，每行包含两个整数 **_N_** 和 **_K_**，用空格分隔。

对于每个测试用例，输出教练可能选择的名字数量，结果取模 **_(10^9+9)_**。

- \(1 \le T \le 10^5\) - \(1 \le N \le 10^5\) - \(1 \le K \le 26\) **本翻译由 AI 自动生成**