Trong một tòa nhà mới xây có ~T~ căn phòng. Nền căn phòng thứ ~i~ có dạng hình chữ nhật với kích thước ~m_i \times n_i~ (~m_i~ đơn vị chiều dài và ~n_i~ đơn vị chiều rộng). Người ta muốn lát sàn phòng này bằng các viên gạch hình vuông giống nhau cùng độ dài cạnh là ~k~, với ~k~ là một số nguyên dương. Hỏi rằng với mỗi căn phòng có bao nhiêu cách chọn loại gạch khác nhau để toàn bộ diện tích của căn phòng được lát kín bằng các viên gạch mà không phải cắt bỏ bất kỳ viên gạch nào. Giả thiết khoảng trống giữa các viên gạch bằng 0.

Yêu cầu: Cho ~T~ căn phòng với kích thước tương ứng, hãy tính số cách chọn gạch cho mỗi phòng.

Input

• Dòng đầu chứa số nguyên dương ~T~ (~T \le 2 \times 10^5~) là số căn phòng.
• Tiếp theo là ~T~ dòng, dòng thứ ~i~ chứa hai số nguyên dương ~m_i, n_i~ (~m_i, n_i \le 5 \times 10^5~) mô tả kích thước nền của phòng thứ ~i~.

Output

Ghi ra màn hình gồm ~T~ dòng, dòng thứ ~i~ ghi duy nhất một số nguyên là số cách khác nhau chọn kích thước viên gạch vuông để lát phòng thứ ~i~.

Sample Input 1

2
12 18
4 3

Sample Output 1

4
1

Giải thích:

• Căn phòng thứ nhất có 4 cách chọn gạch lát nền với kích thước viên gạch là ~k = 1, 2, 3, 6~.
• Căn phòng thứ hai chỉ có duy nhất một cách lát nền với kích thước viên gạch ~k = 1~.

Subtasks

• Có 50% số tests ứng với 50% số điểm của bài có ~T = 1; m_i, n_i \le 100~.
• 25% số tests tiếp theo ứng với 25% số điểm của bài có ~m_i, n_i \le 10^4~.
• 25% số tests còn lại không có ràng buộc bổ sung.