Cho một số nguyên dương \(N\) có dạng \(N = p_1^{k_1} \cdot p_2^{k_2} \cdot \dots \cdot p_m^{k_m}\) (\(p_1, p_2, \dots, p_m\) là các số nguyên tố, \(m > 0, k_i > 0\)).

Ta gọi \(N = x_1 \cdot x_2 \cdot \dots \cdot x_l\) là một cách phân tích của số \(N\) ra thừa số nếu \(x_1 \le x_2 \le \dots \le x_l\) là các số nguyên dương và \(l > 1\). Hai cách phân tích \(N = x_1 \cdot x_2 \cdot \dots \cdot x_l\) và \(N = y_1 \cdot y_2 \cdot \dots \cdot y_h\) được gọi là khác nhau nếu tồn tại \(i\) sao cho \(x_i \neq y_i\) với \(i \le \min(l, h)\).

Yêu cầu: Đếm số cách phân tích khác nhau \(N\) thành tích các thừa số.

Ví dụ: \(N = 30 = 2 \cdot 3 \cdot 5\) ta có \(4\) cách phân tích như sau:

• \(30 = 2 \cdot 3 \cdot 5\)
• \(30 = 2 \cdot 15\)
• \(30 = 3 \cdot 10\)
• \(30 = 5 \cdot 6\)

Input

• Dòng đầu là số \(T\) (\(T \le 100\)) là số bộ dữ liệu.
• \(T\) dòng sau, mỗi dòng chứa một số nguyên dương \(N\) (\(N \le 10^{12}\)).

Output

• Gồm \(T\) dòng, mỗi dòng chứa một số là số cách phân tích khác nhau của từng bộ dữ liệu tương ứng với dữ liệu vào.

Example

2
30
100

4
8