Cơ quan cảnh sát quốc gia Nhật Bản (National Police Agency hay còn gọi là NPA) là cơ quan trung ương của Hệ thống cảnh sát nhật bản,và là cơ quan điều phối trung ương về thực thi pháp luật trong các tình huống khẩn cấp quốc gia ở Nhật Bản. Nghe đến cái tên thôi cũng đã thấy nó rất cool ngầu rồi. Chính vì thế anh Hiếu có dự định sang Nhật và trở thành một sĩ quan cấp siêu cao của NPA. Để đánh giá năng lực của anh Hiếu họ đã đưa ra một bài toán rất khó: Giải phương trình nghiệm nguyên dương.

~\frac{1}{x}~ + ~\frac{1}{y}~ = ~\frac{1}{a.b}~

Thấy bài toán hơi dễ, anh Hiếu quyết định thể hiện mình hơn nữa bằng cách đếm số nghiệm ~x~, ~y~ nguyên dương thỏa mãn phép tính. Cho biết 2 số nguyên ~a~ và ~b~, bạn hãy giúp anh Hiếu với nha.

Input

Dòng đầu là số bộ test ~T~ (~T~ ~\le~ ~5.10^5~)

T dòng tiếp theo mỗi dòng gồm 2 số nguyên dương ~a~ và ~b~ (~0~ ~\lt~ ~a~ ~,~ ~b~ ~\le~ ~10^9~)

Output

Gồm ~T~ số nguyên mỗi số nằm trên 1 dòng là số nghiệm nguyên dương của mỗi bộ dữ liệu

Sample

Input #1

2
1 1
1 2

Output #1

1
3

Hint

~\frac{1}{4}~ số bộ test có ~a~ ~,~ ~b~ ~\le~ ~10^2~ ~,~ ~T~ ~\le~ ~1~

~\frac{1}{4}~ số bộ test có ~a~ ~,~ ~b~ ~\le~ ~10^3~ ~,~ ~T~ ~\le~ ~10~

~\frac{1}{4}~ số bộ test có ~a~ ~,~ ~b~ ~\le~ ~10^9~ ~,~ ~T~ ~\le~ ~100~

~\frac{1}{4}~ số bộ test có ~a~ ~,~ ~b~ ~\le~ ~10^6~ ~,~ ~T~ ~\le~ ~5.10^5~