Description

WY所在社团也想借机会准备搞一个聚会，已经知道现有成员$N$人，把成员从$1$到$N$编号，其中WY的号码是$N$号，凡是和WY是老朋友的，那么该成员的号码肯定和$N$有大于$1$的公约数，否则都是新朋友，现在WY想知道究竟有几个新朋友？请你编程序帮WY计算出来。

Format

Input

第一行是测试数据的组数$CN（Case number，1$

Output

对于每一个$N$，输出一行新朋友的人数，这样共有$CN$行输出。

Samples

2
25608
24027

7680
16016