github.com/captn3m0/codechef.git

---
{"languages_supported":{"0":"NA"},"title":"BBSYSTEM","category":"NA","old_version":true,"problem_code":"BBSYSTEM","tags":{"0":"NA"},"layout":"problem"}
---

<h3> All submissions for this problem are available. </h3><p>
Chef Ciel has forgotten the combination to the safe.
It's a serious incident, because the safe contains this month's waitstaff salaries.
</p>

<p>
To open the safe, <strong>N</strong> boxes and <strong>N</strong> balls are used.
The safe has <strong>N</strong> boxes that numbered from 1 to <strong>N</strong> uniquely.
Each box can contain only one ball.
Now, the box <strong>i</strong> contains one ball that numbered <strong>i</strong>, and the safe is locked.
</p>

<p>
The only things which Ciel remember for unlocking the safe are the followings:
</p>

<ol>
<li>
She must put every ball into some box.
</li>
<li>
Let the box <strong>i</strong> contains the ball <strong>A<sub>i</sub></strong>.
When the safe is opened the number of divisors of <strong>i</strong> equals to the number of divisors of <strong>A<sub>i</sub></strong> for all <strong>i</strong> from 1 to <strong>N</strong>. </li>
</ol>

<p>
How many combinations which satisfy above conditions should she check?
The number of combinations can be very large, so you should print this number modulo 500009 (5*10<sup>5</sup>+9).
</p>

<h3>Input</h3>
<p>
The first line contains an integer <strong>T</strong>, the number of test cases.
Then <strong>T</strong> test cases follow.
The only line of each test case contains an integer <strong>N</strong>.
</p>

<h3>Output</h3>
<p>
For each test case, print the number of combinations modulo 500009 (5*10<sup>5</sup>+9).
</p>

<h3>Constraints</h3>
<p>
1 &le; <strong>T</strong> &le; 100000 (10<sup>5</sup>)<br />
3 &le; <strong>N</strong> &le; 2000000000 (2*10<sup>9</sup>)<br />
</p>

<h3>Sample Input</h3>
<pre>3
3
5
100</pre>

<h3>Sample Output</h3>
<pre>1
5
43264</pre>

<h3>Output details</h3>
<p>
In the first case, the valid combination is
</p>
<pre>Box: 123
Ball: 132</pre>
<p>
since the number of divisors of 2 is equal to the number of divisors of 3.
</p>
<p>
In the second case, the valid combinations are
</p>
<pre>Box: 12345 12345 12345 12345 12345
Ball: 12543 13245 13542 15243 15342</pre>