果冻发现贤者禾枫有文学天赋，于是让她构造剧情线。对于某一章节，贤者一共想了 m 个有区别的剧情分支和 n 个无区别的剧情背景。现要求每个剧情分支必须选择至少一个剧情背景作为基础，且要求每个背景必须被唯一的剧情分支选择。求有多少种剧情背景的选择方案。
输入
首先输入一行一个整数 t ，代表询问的个数。
接下来输入 t 行，每行两个整数，代表 n,m ，用一个空格隔开。
对 20\% 分数的数据，1\le n,m\le8
对 40\% 分数的数据，1\le n,m\le10^3
对 80\% 分数的数据，1\le n,m\le9\times10^4
对 100\% 分数的数据，1\le n,m\le10^{18},m\le n,1\le t\le10^5
输出
输出 t 行，每行一个整数，代表每个询问的选择方案数对质数 99991 取模后的结果。
样例
| 标准输入 复制文本 |
3 5 5 5 2 5 3 |
| 标准输出 复制文本 |
1 4 6 |
提示
对 n=m=5 ，只有一种方案：每个分支选一个背景
对 n=5,m=2 ，可以让两个分支分别选 (1,4),(2,3),(3,2),(4,1) 个背景，共四种方案
对 n=5,m=3 ，可以让三个分支分别选 (1,1,3),(1,3,1),(3,1,1),(1,2,2),(2,1,2),(2,2,1) 个背景，共六种方案