题目描述

给定一个正整数 $n$。你可以反复执行以下两种操作之一：

1. 若 $n>1$，令 $n=n-1$；
2. 任选一个 $n$ 的真因子 $d$（即 $1\le d<n$ 且 $d$ 能整除 $n$），令 $n=\dfrac{n}{d}$。

请你求出把 $n$ 变成 $1$ 的最少操作次数。

输入格式

第一行一个整数 $t$ 表示测试组数，满足 $1\le t\le 1000$。

接下来 $t$ 行，每行一个整数 $n$，满足 $2\le n\le 10^{12}$。

输出格式

对于每组数据，输出两个正整数 $a,b$，满足 $a+b=n$，且 $\operatorname{lcm}(a,b)$ 最小。若有多组答案，输出任意一组即可。

10
1
2
3
4
5
6
7
8
9
10

0
1
2
2
3
2
3
2
3
2