小淘很喜欢研究一些关于质数因子的问题，这天他思考这样的一个问题。 假设现在有一个正整数 ，你需要构造一个数 ，满足下面的两个条件： 的质因数的个数不能超过 个（包含重复的），且这些质因子相乘的恰好等于 ； 让 的优秀因子数量最大化； 优秀因子定义为：若 的某个因子能被 的每一个质因子整除，那么这个因子就是优秀因子，例如， 为 ，则它的因子有 ，它的质因子有 ，其中因子 和 均能被质因子里的所有数整除，故 和 是优秀因子。 现在请你输出让 的优秀因子数量最大化时，这个优秀因子数量有有多少个。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数 代表数据组数，每组测试数据描述如下：在一行输入一个整数  表示待处理的数字。

输出描述:

对于每一组测试数据，在一行上输出一个整数，代表  的优秀因子数量最大化时，这个优秀因子数量有有多少个。由于答案可能很大，请将答案对 取模后输出。