题目描述

在本题中，我们来定义一个数列f，用f[n]表示这个数列的第n项。f[1] = 1。

从第2项开始，这个数列满足以下规律。

(1)如果n是质数，那么f[n] = n - 1。

(2)如果n可以分解成2个互质的数的乘积，即n = a×b，且a和b是互质的，那么f[n] = f[a]×f[b]。如果n还可以分解成另外2个互质的数的乘积，比如n = a1×b1，且a1和b1是互质的，这个数列保证f[n] = f[a1]×f[b1]也成立。

【提示】一个自然数n，可能可以分解成多对互质的数a和b的乘积。例如，30=5×6、30=2×15，30=3×10，30=1×30，5和6是互质的，2和15是互质的，3和10是互质的，1和30也是互质的。

注意：以上第(2)点，n如果分解成n = 1×n，1和n是互质的，那么根据第(2)点，f[n]=1×f[n]，也是成立的，但这不能用来求f[n]。

(3)如果n不能分解成2个互质的数a、b的乘积（a, b不为1），此时n一定就只有一个质因数，即n = $p^i$，p为质数，那么f[n] = n - n/p。

在本题中，输入一个自然数n，n≤100000，求f[n]并输出。

输入格式

输入数据第一行为一个正整数q，表示测试数据的个数。接下来有q行，每行为一个正整数n，n≤100000。

输出格式

对每个测试数据中的n，输出一行，为f[n]的值。

输入输出样例 #1

输入 #1

3
7
27
30

输出 #1

6
18
8

说明/提示

本题出处

本题源自以下教材的编程习题：王桂平, 周思益, 周迎川著. C++编程与信息学竞赛数学基础, 北京大学出版社, 2025年7月出版.