「ACOI2020」学园祭

 秋天，是学习之秋，食欲之秋，更是，学园祭之秋！随着时间流逝，学园祭也越来越近。终于等到这一天，可是没想到在冲绳岛上邂逅到女装的渚同学的勇次竟然来了！中村 莉櫻（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$。