小苯定义一个数字的权值为：该数字的因子个数。 小苯现在拿到了一个正整数 ，他希望将 分解为若干不等于 的数字（也可以不做分解），使得所有分解出的正整数乘积等于 ，且所有数字的权值之和尽可能大，你能帮帮他求出最大的权值吗。

输入描述:

输入包含 行。第一行一个正整数 ，表示数据组数。接下来 行，每行一个正整数 ，表示每组数据中小苯询问的数字 。

输出描述:

输出包含 行，每行一个正整数表示每组测试数据的最大权值和。