球与盒子

你有�个球，标号为 1,2, …, �。

你想把它们放到标号为 1,2, …, �的盒子里。要求

• 每个盒子里恰好有一个球；

• 如果盒子�里面的球的标号是��，那么�� 的因子个数，必须和�的因子个数相 同；

由于答案可能很大，输出答案对 500009 取模的值。

输入格式 第一行一个整数�表示数据组数。

接下来�行，每行一个整数�。

输出格式 对于每组数据，输出一行，一个数值表示答案。

样例输入 3 3 5 100

样例输出 2 6 43265

数据规模 共 10 组数据。

测试点 1,2 满足 1 ≤ � ≤ 10。

测试点 3,4 满足 1 ≤ � ≤ 103 。

测试点 5,6,7 满足 1 ≤ � ≤ 106 。

对于 100% 的数据，满足 1 ≤ � ≤ 105 , 1 ≤ � ≤ 109 。