Background

”这怕不是个假题吧！“----刘学习

Description

Format

刘学习是个数论天才，有一天他遇到了如下问题：
1.对于给定正整数n，刘学习希望知道在1到n的所有正整数中与n互质的数的个数是奇数还是偶数。
2.对于给定正整数n，刘学习希望知道在1到n的所有正整数中最大的与n互质的数
(如果两个正整数a,b的最大公约数为1,则认为a,b互质)

Input

第一行有一个正整数T有T组数据
对于每一组数据
一个正整数n

Output

对于每组数据
输出一行两个数x y，用空格分开
x为1到n的所有正整数中与n互质的数的个数的奇偶性(偶数输出0 奇数输出1)
y为1到n的所有正整数中最大的与n互质的数

Sample 1

Input

2
2
4

Output

1 1
0 3

Limitation

1s, 64Mbfor each test case.

Hint

T<=100
对于所有测试数据0<n<=10000000000
对于10%的测试数据 n<=10
对于20%的测试数据 n<=100
对于30%的测试数据 n<=1000
对于50%的测试数据 n<=10000
对于100%的测试数据 n<=10000000000

Source

lyhlyhlyh