F. Coprime
time limit per test
5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

"Why did it come to this? I finally met someone I love, and also gained a lifelong best friend. Two kinds of joy blend together, and this double joy brings endless more happiness. I was supposed to embrace a dreamlike happy life. But why... why has everything turned out like this?"

Given a positive integer $$$n$$$, consider all positive integers in the interval $$$[n, n^2]$$$.

A positive integer $$$k$$$ is defined as good if it meets both of the following requirements:

  • $$$n \le k \le n^2$$$.
  • For any positive integer $$$i$$$ in $$$[n, n^2]$$$ where $$$i \neq k$$$, we have $$$\gcd(i, k) = 1$$$.

For the given $$$n$$$, you are required to:

  • Count how many good positive integers exist in $$$[n, n^2]$$$;
  • Output any one of these good positive integers.
Input

The first line contains a positive integer $$$T$$$ $$$(1 \le T \le 5000)$$$, indicating the number of test cases. Each of the next $$$T$$$ lines contains a positive integer $$$n$$$ $$$(1 \le n \le 5000)$$$.

Output

For each test case, output two lines. The first line contains a non-negative integer $$$c$$$, representing the number of good integers in $$$[n, n^2]$$$. The second line contains a positive integer $$$k \in [n, n^2]$$$ which is a good integer. If there are multiple answers, you may output any of them.

As a special case: if no good integer exists in $$$[n, n^2]$$$, output $$$0$$$ on the first line and $$$-1$$$ on the second line.

Example
Input
5
1
2
3
4
5
Output
1
1
1
3
2
5
2
11
4
13