题目描述

“质数是在一个大于1的自然数中，除了1和此整数自身外，没法被其他自然数整除的数 ". 现在有一个问题，想让聪明的你来解决 $:$ 现在有 $t$ 组数据，每组数据中有一个 $l$ 和一个 $r$ ,现在请你输出第 $l$ 个质数 $(a)$ 以及第 $r$ 个质数 $(b)$ ,以及 $a ^ b$ ($a$ 的 $b$ 次方).

由于该数据可能非常大，请你对 $1e9 + 7$ 取余. $ps :$ $1e9 + 7$ $=$ $1000000007$.

输入

第一行一个整数 $t$ ,代表有 $t$ 组数据。 接下来的 $t$ 行，每行两个整数 , $l$ 和 $r$, 分别表示第 $l$ 个以及第 $r$ 个.

输出

输出 $t$ 行，每行三个整数，分别代表第 $l$ 个质数，第 $r$ 个质数，以及 $a ^ b$ 取余后的结果. $a$ 和 $b$ 的含义看题目.

样例一

2
1 2
3 4

2 3 8
5 7 78125

样例解释

第二组数据中，第 $3$ 个质数为 $5$，第 $4$ 个质数为 $7$ , $5 ^ 7$ % $(1e9 + 7)$ $= 78125$

数据范围

$1 \leq t \leq 10 ^ 5$

保证 $1 \leq l \leq r \leq 78498$ ，并且最大的质数不超过 $10 ^ 6$.