G. Product Partition
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given three integers $$$n$$$, $$$L$$$, and $$$R$$$.

You need to do the following:

  • Pick an integer $$$m$$$ such that $$$1 \leq m \leq n$$$;
  • Partition the interval $$$[1, n]$$$ into $$$m$$$ intervals $$$[l_1, r_1], [l_2, r_2], \ldots, [l_m, r_m]$$$ such that:
    • $$$l_1 = 1$$$ and $$$r_m = n$$$;
    • $$$l_i \leq r_i$$$ for all $$$1 \leq i \leq m$$$;
    • $$$r_i = l_{i+1} - 1$$$ for all $$$1 \leq i \lt m$$$;
    • $$$L \leq r_i - l_i + 1 \leq R$$$.

Note $$$P_i= \Pi_{l_i}^{r_i}i$$$. Find the minimum of $$$\gcd(P_1, P_2,\ldots,P_m)$$$, and output your interval partition scheme. Here, $$$\gcd$$$ means greatest common divisor.

For example, $$$n=7$$$, $$$L=3$$$ and $$$R=4$$$, one optimal scheme is to choose $$$m=2$$$ and intervals $$$[1,4]$$$ and $$$[5,7]$$$. In this case, $$$\gcd(P_1,P_2)=\gcd(1 \cdot 2 \cdot 3 \cdot 4,5 \cdot 6 \cdot 7)=\gcd(24,210)=6$$$, which can be proven to be the minimum value.

Since the value of $$$\gcd(P_1, P_2,\ldots,P_m)$$$ may be large, you need to output it modulo $$$998\,244\,353$$$. If there is not any valid interval partition scheme, output $$$-1$$$ instead.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The only line of each test case contains three integers $$$n$$$, $$$L$$$, and $$$R$$$ ($$$1 \le n \le 10^5$$$, $$$1 \le L \le R \le n$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output

For each test case, if there is not any valid interval partition scheme, output $$$-1$$$.

Otherwise, in the first line output two integers $$$m$$$ and $$$g$$$, where $$$m$$$ is the number of intervals and $$$g$$$ is the minimum value of $$$\gcd(P_1, P_2,\ldots,P_m)$$$ modulo $$$998\,244\,353$$$.

In the following $$$m$$$ lines, output two numbers $$$l_i$$$ and $$$r_i$$$, representing the left and right endpoints of the intervals. The intervals must satisfy all the conditions in the statement.

If there are multiple answers, output any.

Example
Input
5
5 3 4
7 3 4
8 3 4
3 1 1
13 7 13
Output
-1
2 6
1 4
5 7
2 24
1 4
5 8
3 1
1 1
2 2
3 3
1 237554682
1 13
Note

In the first test case, there is not any valid interval partition scheme.

In the second test case, the explanation is shown in the statement above.