Có một quả bóng ở góc trên bên trái của một lưới \(n \times m\). Các hàng của lưới được đánh số \(1,2,\dots,n\), và các cột được đánh số \(1,2,\dots,m\).

Ban đầu quả bóng di chuyển theo đường chéo ra xa góc trên bên trái. Ở mỗi bước, nó di chuyển một ô. Mỗi khi quả bóng chạm biên của lưới, nó đổi hướng.

Sau bao nhiêu bước thì quả bóng trở lại vị trí ban đầu? Số ô khác nhau mà nó đã đi qua là bao nhiêu?

Đầu vào

Dòng đầu tiên chứa một số nguyên \(t\): số lượng bộ kiểm thử.

Sau đó có \(t\) dòng. Mỗi dòng chứa hai số nguyên \(n\), \(m\): kích thước của lưới.

Đầu ra

Với mỗi bộ kiểm thử, in hai số nguyên: số bước và số ô đã đi qua.

Constraints

• \(1 \le t \le 1000\)

• \(2 \le n,m \le 10^9\)

Example

4
3 4
2 2
19 18
42 1337

12 6
2 2
612 171
109552 28077