题目描述

你有$n$个球，标号为 $1,2, …, n$。 你想把它们放到标号为 $1,2, …, n$的盒子里。要求 • 每个盒子里恰好有一个球； • 如果盒子$i$里面的球的标号是$A_i$，那么$A_i$的因子个数，必须和$i$的因子个数相同； 由于答案可能很大，输出答案对 $500009$ 取模的值。

输入格式

第一行一个整数$T$表示数据组数。 接下来$T$行，每行一个整数$n$。

输出格式

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

3
3
5
100

2
6
43265

数据规模

共 10 组数据。 测试点 1,2 满足 $1 ≤ n ≤ 10$。 测试点 3,4 满足 $1 ≤ n ≤ 10^3$。 测试点 5,6,7 满足 $1 ≤ n ≤ 10^6$。 对于 100% 的数据，满足 $1 ≤ T ≤ 10^5, 1 ≤ n ≤ 10^9$。