象棋

本题和F题是一样的.

题目描述

lhy 和 zys 喜欢一起下象棋. 最近 lhy 学会了新招, 棋力大涨之下, 他对 zys 的胜率 p > 0.5. zys 不喜欢被虐菜的感觉, 所以他想要在净负 2 盘之后就去学习棋谱. 现在 lhy 想要知道他们一共可以下的盘数 n 的期望. 本题有多组测试用例.

数据格式

输入

第一行, 一个正整数 T, 表示测试用例的组数.

每行两个正整数n, m 表示概率 p = $\frac{m}{n}$.

输出

每行一个期望的盘数 n, 答案对 $10^9+7$ 取模.

样例

输入

2
1 1
10 10

输出

2
2

样例解释

两个样例的概率都是 p = 1, 所以在连赢两盘后就结束了.

数据范围及约定

$T \le 10^5, 0 < m \le n \le 10^9$.