곱셈적 함수의 값

양의 정수 $X$가 주어진다. 오일러 피 함수 $\varphi(X)$는 $1$ 이상 $X$ 이하의 정수 중 $X$와 서로소인 정수의 개수이다. 뫼비우스 함수는 $\mu(1)=1$이고, $X$가 소수의 제곱으로 나누어떨어지면 $\mu(X)=0$이다. 그 외에 $X$가 서로 다른 $K$개 소수의 곱이면 $\mu(X)=(-1)^K$이다.

$X$에 대해 다음 여섯 값을 구해 보자.

• $X$의 최소 소인수와 그 지수
• 오일러 피 함수 $\varphi(X)$와 뫼비우스 함수 $\mu(X)$
• $X$의 양의 약수의 개수와 합

$X$가 소수이면 최소 소인수를 $0$, 지수를 $1$로 표시한다. $X=1$이면 최소 소인수와 지수는 모두 $0$이고, 나머지 네 값은 모두 $1$이다.

첫 번째 줄에 $X$의 상한을 의미하는 정수 $N$과 질의의 수를 의미하는 정수 $Q$가 공백으로 구분되어 주어진다. $(1 \le N \le 2 \cdot 10^6; 1 \le Q \le 200\,000)$

두 번째 줄부터 $Q$개의 줄에 걸쳐 정수 $X$가 주어진다. $(1 \le X \le N)$

질의가 주어진 순서대로 각 질의의 $X$에 대한 최소 소인수, 그 지수, $\varphi(X)$, $\mu(X)$, 양의 약수의 개수, 양의 약수의 합을 공백으로 구분하여 한 줄에 출력한다.