你说得对，但是我不玩原神，我玩【数据删除】。
给定正整数 ，求：
其中 是数论莫比乌斯函数，其定义为：
存在一个大于的因子是完全平方数否则，其中表示的质因子个数
答案对于 取模。
本题包含多组测试数据。
输入的第一行包含一个整数 ，表示测试数据的组数。
接下来包含 组数据，每组数据的格式如下：
第一行包含一个整数 。
对于每组测试数据输出一行，包含一个整数，表示答案对 取模的结果。
3 1 3 5
1 3 43
