• Trong hệ trục tọa độ Descartes, cho các điểm: ~O(0, 0), A(a, 0)~ và ~B(0, b)~. Hãy đếm số điểm có tọa độ nguyên nằm trên và nằm trong ~ΔOAB~.

Input

Dòng đầu tiên ghi số nguyên dương ~T~ là số lượng câu hỏi,

Dòng thứ ~i~ trong ~T~ dòng tiếp theo là câu hỏi thứ ~i~ chứa hai số nguyên dương ~a, b~.

Giới hạn:

• ~(1 \le T \le 100)~,
• ~(1 \le a, b \le 10^9)~.

Output

Gồm ~T~ dòng, dòng thứ ~i~ để trả lời cho câu hỏi ~i~ chứa hai số nguyên dương là kết quả của bài toán.

Sample

Input #1

2
2 4
1 1

Output #1

8 1
3 0

Hint

Ở câu hỏi ~1~, ta sẽ có tam giác như sau:

Ta có thể thấy:

• ~8~ điểm có tọa độ nguyên ở trên tam giác(điểm màu xanh),
• ~1~ điểm có tọa độ nguyên bên trong tam giác(điểm màu đen).