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

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

输入包括 T+1 行。

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

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

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

尽可能的分成每份 3 个。如果多余 1 的时候，应该把其中的一个 3 和这个 1 凑成 2 和 2。