题目背景

中秋赛的数论惨遭暴力和各种奇奇怪怪的做法秒切，特此加强了数据

题目描述

有T个问题，每个问题给定一个正整数n，已知p,q是一对互质数，求满足p*q为n的因数的正整数对(p,q)个数。

注：公因数只有1的两个非零自然数，叫做互质数。 1和任何一个大于1的自然数在一起都是互质数。

输入格式

第1行，一个正整数T

第2行至第T+1行，每行一个正整数n

输出格式

对每一个问题，输出一行整数表示数对(p,q)的个数

测试样例

12
7945137
593137
1559156
2086495
3783512
8601084
1956522
5237608
2117449
7680469
8224825
9634578

44
26
44
26
20
74
26
20
26
2
134
80

数据范围

对所有数据，满足$T\leq 10^6$,$n\leq 10^7$

提示

本题唯一指定AC做法——线性筛，有其他做法能过的欢迎来投诉