时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
Wjc loves Euler's totient function. One day, he noticed such a problem on bitoj, whose statement is:
"For a given , calculated the value of
, where
is equal to the number of
such that
and
. For example,
and
."
Since this problem is exactly about Euler's totient function, Wjc solved it with O(1) complexity by his mouth. However, such an easy problem didn't satisfy him and he prepared another problems by himself.
Now, this new problem satisfied him a lot and he wondered if you're a real genius(when we say "real genius", it just means "as clever as wjc") that you are able to solve this problem.
The problem is, for a positive interger , we define
as :
Since wjc don't like ,the domain of
is all intergers except one. That is,
is an illegal value for
.
Based on the defination of , two problems are put forward by wjc and they are:
-
You are supposed to answer the
such that
achieve the MININUM value of
where
. If there are mutiple
-
You are supposed to answer the
输入描述:
The first line contains a single interger
, which means the numbers of test case.
For the next
lines, each line contains a single interger
, the numbers that wjc gives you.
输出描述:
For each test, you are supposed to output two space-separated number, where the first number is your answer to the first problem of wjc and vice versa.
If
, just output
to show
is undefined.
备注:
The value of
range from
to
are
.
Please note that both
and
can make
.