暂无测试数据。

蒜头君喜欢旅游，有次他在撒哈拉大沙漠中惊喜的捡到了一个神灯，这个神灯可以满足他一个愿望，机智的蒜头君当机立断许愿成为一个亿万富翁，但是神灯的神力是有限的，他只能通过蒜头君现有的钱来变出更多的钱，而且只能变一次。

现在蒜头君可以将自己身上带的钱分成任意多份（每份的价值均为正整数），然后神灯会把每份的价值相乘的结果作为最终的金额返还给蒜头君，蒜头君没有随身携带计算器，但他迫切想知道自己最多能获得多少钱，希望你可以告诉他答案。

输入格式

输入包括 $T+1$ 行。

第一行为一个正整数 $T$，代表样例的个数（$1 \le T \le 10$) 。

接下来 $T$ 行，每行输入一个非负整数 $n$，代表蒜头君身上所有钱的价值和。（$0 \le n \le 100000$）。

输出格式

每组数据有 $T$ 行输出，每行输出的结果为一个正整数，代表蒜头君最多获得的钱数，由于计算结果可能会很大，请将结果对 $10^9 + 7$ 取模后再输出。

2
0
2

0
2