题目背景

秋天，是学习之秋，食欲之秋，更是，学园祭之秋！随着时间流逝，学园祭也越来越近。终于等到这一天，可是没想到在冲绳岛上邂逅到女装的渚同学的勇次竟然来了！中村 莉櫻（Nakamura Rio）见到这个情况，忙给渚同学换上女装。没办法，勇次已经来了，于是渚同学鼓起勇气迈出了第一步。（为什么自顾自地加提示框啊喂！）

题目描述

莉櫻为了利用这个人傻钱多的少爷，尽全力提高消费额，努力地暗示渚同学。没办法，于是渚同学想了一下，提出了一个问题：

给出一个 $n$，定义：

$$\Gamma(0)=1,\Gamma(n)={n!}$$ $$A_i^j=\frac{\Gamma(i)}{\Gamma(j)}$$

求

$$\sum_{i=1}^n \sum_{j=1}^i \sum_{k=1}^j \gcd(A_{i-j}^j \times \Gamma(j),A_{j-k}^k \times \Gamma(k)) $$

渚同学念着莉櫻举起的对话板上写的字：如果不能在规定时间回答出问题的话，就要把菜单全部买一遍哦！

尽管勇次钱多，但是他并不想吃得太多，因为这个问题有 $T$ 个小问题！

由于答案可能太大，请将答案对 $10086001$ 取模。

输入格式

本题有多组数据。

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

对于每组数据：

只有一行一个整数 $n$。

输出格式

对于每组数据，一行一个整数，表示问题的答案对 $10086001$ 取模后的值。

5
1
2
3
4
5

1
4
10
20
36

提示

数据范围

本题采用捆绑测试。

• Subtask 1（20 points）：$T \leq 10^3$，$n \leq 10^2$。
• Subtask 2（30 points）：$T \leq 10^6$，$n \leq 5 \times 10^3$。
• Subtask 3（50 points）：$T \leq 10^6$，$n \leq 10^6$。

对于 $100\%$ 的数据，$1 \leq T,n \leq 10^6$。