Nền một căn phòng có dạng hình chữ nhật kích thước ~m\times n~. Cần lát kín nền bằng các viên gạch hình vuông cạnh nguyên dương ~k~ mà không phải cắt gạch.

Với mỗi căn phòng, hãy đếm số cách chọn ~k~.

Input

Dòng đầu chứa số căn phòng ~T~.

~T~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương ~m,n~.

Output

In ra ~T~ dòng, mỗi dòng là số cách chọn kích thước gạch cho căn phòng tương ứng.

Subtask

• 50% số điểm: ~T=1~, ~m,n \le 100~.
• 25% số điểm: ~m,n \le 10^4~.
• 25% số điểm: ~T \le 2\cdot 10^5~, ~m,n \le 5\cdot 10^6~.

Ví dụ

2
12 18
4 3

4
1