题目描述

你有 $n$ 个球，标号为 $1,2,\dots,n$。

你想把它们放到标号为 $1,2,\dots,n$ 的盒子里。要求

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

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

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

输入格式

第一行一个整数 $T$ 表示数据组数。

接下来 $T$ 行，每行一个整数 $n$。

输出格式

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

样例

3
3
5
100

2
6
43265

数据规模与约束

共 10 组数据。

测试点 1,2 满足 $1 \le n \le 10$。

测试点 3,4 满足 $1 \le n \le 10^3$。

测试点 5,6,7 满足 $1 \le n \le 10^6$。

对于 $100\%$ 的数据，满足 $1 \le T \le 10^5$，$1 \le n \le 10^9$。