我们一般称 中与 互质的数的个数为欧拉函数，记为 。 现在，你需要构建一个能够维护欧拉函数信息的数据结构，使得其能支持： 欧拉函数查询：输出 。

输入描述:

第一行输入一个整数 代表操作次数。此后 行，每行输入一个整数 代表欧拉函数查询。

输出描述:

对于每一次询问，在一行上输出一个整数，代表所求的欧拉函数。