Ước số

Cho hai số nguyên dương \(a\) và \(b\). Hãy đếm số lượng ước nguyên dương của tích \(a\) và \(b\).

Input

Dữ liệu vào từ bàn phím gồm:

• Dòng 1: chứa số nguyên dương \(T\) (\(T \le 10^4\)) là số bộ số \((a, b)\).

• \(T\) dòng tiếp theo, mỗi dòng chứa một bộ số nguyên dương \(a, b\) (\(a, b \le 10^6\)).

Ràng buộc:

• Có \(80\%\) số test có \(T = 1\); \(a, b \le 10^3\).

• Có \(20\%\) số test còn lại có \(T = 10^4\); \(a, b \le 10^6\).

Output

Ghi ra màn hình gồm \(T\) dòng, mỗi dòng chứa một số nguyên là số lượng ước nguyên dương của tích \(a\) và \(b\) tương ứng với dữ liệu vào.

Example

Input:

2
2 4
6 7

Output:

4
8

Note

• Tích của \(2 \times 4 = 8\), số \(8\) có \(4\) ước nguyên dương.

• Tích của \(6 \times 7 = 42\), số \(42\) có \(8\) ước nguyên dương.