题目背景

A piece to the puzzle of construction, the parts may be different sizes, but all are just as integral to the end result...

注：你不需要阅读本题的题目背景，因为它和题目没有一点关系。

在【数据删除】，现实以最完美的方式失败了。作为3d网格故障，回忆笼罩着你的思绪并且仍然是你的手。外面是多么迷人的一天啊。为什么我们不去散散步呢，你和我？周围没有其他人，只有你和错误着的风景。你如此开心，你淹没在甜蜜的空气中并独自一人的清爽着，就像一个表面正在等候一个洞。

题目描述

定义一个数列 $a$ 是正整数 $n$ 的合法拆分当且仅当 $\displaystyle \sum_{i \in a}i=n$ 且数列 $a$ 中的每个元素均为正整数。

定义一个数列 $a$ 的价值 $w$ 为 $\displaystyle \prod_{i \in a}i$。

现在给出一个正整数 $n$，求出 $n$ 的所有合法拆分中的最大价值。

例如当 $n=4$ 时，所有的合法拆分为 $[4],[1,3],[2,2],[3,1],[1,1,2],[1,2,1],[2,1,1],[1,1,1,1]$，其中数列 $[4]$ 和 $[2,2]$ 的价值最大，均为 $4$，所以 $4$ 的所有合法拆分中的最大价值为 $4$。

由于这个最大值可能很大，所以你只需要输出这个最大值对 $1145141919810$ 取模后的结果。

如果你没看懂，不妨来看看下面的更通俗的定义。（上面的定义更严谨）

定义一个数列 $a$ 是正整数 $n$ 的合法拆分当且仅当 $a$ 中的所有元素之和恰好为 $n$ 且数列 $a$ 中的每个元素均为正整数。

定义一个数列 $a$ 的价值 $w$ 为 数列 $a$ 中的所有元素之积。

现在给出一个正整数 $n$，求出 $n$ 的所有合法拆分中的最大价值。

输入格式

本题多测。

第一行一个正整数 $T$。

随后 $T$ 行每行一个正整数 $n$。

输出格式

$T$ 行表示每组数据中 $n$ 的所有合法拆分中的最大价值对 $1145141919810$ 取模后的结果。

样例 #1

样例输入 #1

1
4

样例输出 #1

4

提示

对于 $10\%$ 的数据，$1\le n\le 10$。

对于 $60\%$ 的数据，$1\le n\le 10^6$。

对于 $100\%$ 的数据，$1\le n\le 10^{12}$，$1\le T \le 100$。

你以为这套题结束了么，其实还有4题，这些只是签到题……