Description

贝西正在为二月份的美国计算机奧林匹克竞赛准备测试用例。

每分钟，她可以选择不准备任何测试用例， 不消耗能量；或者消耗 $3^{a-1}$ 的能量准备 $a$ 个测试用例，其中 $a$ 是一个正整数。

农场主约翰有 $D\left(1 \leq D \leq 2 \cdot 10^5\right)$ 个要求。对于第 $i$ 个要求，他告诉贝西在前 $m_i$ 分钟内，她需要总共准备至少 $b_i$ 个测试用例 $\left(1 \leq m_i \leq 10^6, 1 \leq b_i \leq 10^{12}\right)$ 。 令 $e_i$ 为满足前 $i$ 个要求时贝西需要消耗的最小能量。

打印 $e_1, \ldots, e_D$ 模 $10^9+7$ 的结果。

Format

Input

第一行包含 $D_{\text {。 }}$ 。接下来的 $D$ 行中，第 $i$ 行包含两个用空格分隔的整数 $m_i$ 和 $b_i$ 。

Output

输出 $D$ 行，第 $i$ 行包含 $e_i \bmod 10^9+7$ 的结果。

Samples

4
5 11
6 10
10 15
10 30

21
21
25
90

对于第一个测试用例:

• $i=1$ : 如果贝西在前 5 天分别创建了 $[2,3,2,2,2]$ 个测试用例，她将会消耗 $3^1+3^2+3^1+3^1+3^1=21$ 单位的能量，并在第 5 天结束时创建了 11 个测试用例。
• $i=2$ : 贝西可以遵循上述策略来确保在第 5 天结束时创建了 11 个测试用例，这将自动满足第二个要求。
• $i=3$ : 如果贝西在前10天分别创建了 $[2,3,2,2,2,0,1,1,1,1]$ 个测试用例，她将会消耗25单位的能量并满足所有要求。可以证明，她不能再减少能量消耗了。
• $i=4$ : 如果贝西在前 10 天每天都创建 3 个测试用例，她将会消耗 $3^2 \cdot 10=90$ 单位的能量并满足所有要求。

对于每个 $i$ ，都可以证明贝西在满足前 $i$ 个要求时不能再减少能量消耗了。

2
100 5
100 1000000000000

5
627323485

20
303590 482848034083
180190 112716918480
312298 258438719980
671877 605558355401
662137 440411075067
257593 261569032231
766172 268433874550
8114 905639446594
209577 11155741818
227183 874665904430
896141 55422874585
728247 456681845046
193800 632739601224
443005 623200306681
330325 955479269245
377303 177279745225
880246 22559233849
58084 155169139314
813702 758370488574
929760 785245728062

108753959
108753959
108753959
148189797
148189797
148189797
148189797
32884410
32884410
32884410
32884410
32884410
32884410
32884410
3883759
3883759
3883759
3883759
3883759
3883759

Limitation

• Inputs 4-5: $D \leq 100$ and $m_i \leq 100$ for all $i$
• Inputs 6-8: $D \leq 3000$
• Inputs 9-20: No additional constraints.