L. 502 Bad Gateway
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Welcome to the Internet Connection Practice Competition (ICPC) this year! In the competition, you and your teammates will fight against the Obstacle Maker System (OMS) to connect to the server successfully! Be careful with every refresh operation, as the system may assign you unknown obstacles.

To simplify the problem, we model the competition process into the following form:

Each team has a timer during the competition, and the goal is to get the remaining time to $$$0$$$ as quickly as possible. At the beginning of the $$$0$$$-th second, the OMS will uniformly and randomly generate an integer $$$t_0$$$ in $$$[1, T]$$$ and initialize the remaining time of your timer to $$$t_0$$$ seconds. Next, at the end of each second (starting with the $$$0$$$-th second), the following events occur in order:

  • The remaining time of the timer will be decreased by $$$1$$$. If the remaining time of the timer is zero at this time, the number of seconds from the start of the competition to this moment is your penalty.
  • Otherwise, you can do nothing after this or use the refresh operation on OMS once. If you choose to refresh your timer, OMS will uniformly and randomly generate a new integer $$$t'$$$ in $$$[1, T]$$$ and set the remaining time of your timer to $$$t'$$$.

Your goal is to minimize your penalty. Please calculate the expected penalty using the optimal strategy. During the contest, you always know the remaining time of the timer, and the value of $$$T$$$.

Input

The first line contains a single integer $$$n\ (1\le n\le 10^6)$$$, representing the number of test cases.

For the following $$$n$$$ lines, each line contains a single integer $$$T_i\ (1\le T_i\le 10^9)$$$, representing the interval for generating random numbers is $$$[1,T_i]$$$ for the $$$i$$$-th test case.

Output

For each test case, output a single line with two positive integers $$$x_i,y_i$$$ where $$$\text{gcd}(x_i,y_i)=1$$$, representing the expected penalty using the optimal strategy is $$$x_i/y_i$$$. It can be proved that the answer can always be described as a fraction.

Example
Input
3
1
2
3
Output
1 1
3 2
2 1