题目描述

在遥远的王国里，骑士 dash 接到了一个重要的任务：他必须将一块神秘的宝石碎片切割成几段，这些段的长度必须是整数，且每段的长度都要互不相同。dash 知道，要完成这项任务，他需要找到一种分割方式，使得这些段的长度乘积达到最大化。

现在，dash 需要你的帮助。请你找到一种最佳的切割方案，使得这些不同长度的小段的乘积最大，并告诉 dash 这个最大的乘积是多少。

输入格式

第一行给定整数 $T$，代表测试组数。

接下来 $T$ 行。每行包含一个整数 $x$，代表宝石碎片的长度。 $1≤T≤10^6,1≤x≤10^9$

输出格式

最大乘积 $S$ 对 $10^9+7$ 取余

样例

1
4

4

最佳策略是 $4=4$