拆分

题目描述

⼩ A 想将正整数 拆分成若⼲个正整数之和，并最⼤化拆分后的正整数之积。⼩ A 希望你帮他计算出拆分后正整数 之积的最⼤值。由于答案可能很⼤，你只需要求出答案对 取模的结果。 形式化地， 的拆分是满⾜ 的若⼲个正整数 ，其中 。你需要求出 的所有拆 分中 的最⼤值对 取模的结果。

输入格式

第⼀⾏，⼀个正整数 ，表⽰数据组数。 对于每组数据：⼀⾏，⼀个整数 ，表⽰给定的正整数。

输出格式

对于每组数据：输出⼀⾏，⼀个整数，表⽰ 拆分后正整数之积的最⼤值对 取模的结果。

样例输入 #1

3
5
8
100

样例输出 #1

6
18
755407364

数据范围

对于 的测试点，保证 。 对于所有测试点，保证 ， 。

知识点与难度

本题涉及的知识点从属于 GESP 7级，难度等级：⭐⭐⭐⭐⭐⭐ 。

测试点分布

生测试数据后，按实际 subtask 分组改写上表。