你需要书写一个程序，使得其能够支持如下操作： 欧拉函数查询：对于给定的整数 ，输出 。 【名词解释】 互质：多个整数的最大的共有约数（简称最大公约数，gcd）如果恰好为 ，被称为它们为互质的。例如， 和 的公约数有 ，其中最大的约数是 ，所以它们不是互质的； 和 的公约数仅有 ，所以它们是互质的。 欧拉函数：指整数 中，与 互质的数的个数，记为 。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数 代表数据组数，每组测试数据描述如下：在一行上输入一个整数 ，表示待查询的数字。

输出描述:

对于每一组测试数据，新起一行输出一个整数，表示 的值。