請仔細閱讀題敘

在數論中，對正整數n，歐拉函數$\varphi (n)$是小於或等於n的正整數中與n互質的數的數目。此函數以其首名研究者歐拉命名，它又稱為$\varphi$函數（由高斯所命名）或是歐拉總計函數（totient function，由西爾維斯特所命名）。

例如$\varphi (8)=4$，因為1,3,5,7均和8互質。

--Wikipedia

那要怎麼求出$\varphi(n)$呢

我們可以先假設$n$的標準分解式$$n = p_1^{a_1}\;\times\;p_2^{a_2}\;\times\;...\;\times\;p_k^{a_k}$$

因為歐拉函數是要求小或等於n的正整數且與n互質的數的數目，所以對於所有$n$的質因數$p_i$的倍數，皆不可能滿足條件

因此我們可以考慮排容原理來計算$\varphi(n)$ $$1.\varphi(n) = n - \frac{n}{p_1} - \frac{n}{p_2} - ... - \frac{n}{p_k}\\ + \frac{n}{p_1p_2} + \frac{n}{p_1p_2} + ... + \frac{n}{p_{k - 1}p_k}\\-\frac{n}{p_1p_2p_3}... \\ 2.\varphi(n) = n - \sum\limits_{S \subseteq \{p_1, p_2, ..., p_k\}}  (-1)^{|S|} \frac{n}{\prod\limits_{p_i \in S}p_i}$$

很電的你一定知道如果要計算上面的算式需要$O(2^kk)$的時間，甚至可能比暴力檢查還慢

其實可以只要仔細觀察第$1$個式子就可以發現，對於選奇數個$p_i$而言為負，偶數個為正

是不是很像某種公式的展開?

首先我們先把$n$提出來，那剩下就變成$$\frac{\varphi(n)}{n} = 1- \frac{1}{p_1} - \frac{1}{p_2} - ... - \frac{1}{p_k}\\ + \frac{1}{p_1p_2} + \frac{1}{p_1p_2} + ... + \frac{1}{p_{k - 1}p_k}\\-\frac{1}{p_1p_2p_3}... \\ = 1^k + 1^{k - 1} \cdot \frac{-1}{p_1} + 1^{k - 1} \cdot \frac{-1}{p_2} \\ + 1^{k - 2} \cdot \frac{-1}{p_1} \cdot \frac{-1}{p_2} + ... + 1^{k - 2} \cdot \frac{-1}{p_{k-1}} \cdot \frac{-1}{p_k}\\ + ...$$

之後的轉換就不刁難程設班的各位了，轉換過後的公式如下$$\varphi(n) = n(1 - \frac{1}{p_1})(1 - \frac{1}{p_2})...(1 - \frac{1}{p_k})$$

時間複雜度順利來到$O(k)$!

現在請你幫忙計算$\varphi$函數吧 !

$\forall\;1\leq n\leq 10^{12},\; 1\leq T \leq 10$

Subtask:

$(5 + 5)\%\;\;n\leq10^2$

$(45 + 45)\%\;\;$無特別限制