TRÍ không như các bạn con trai khác, TRÍ rất thích xếp hạc giấy.

Vì thế trong dịp tháng COLD HOLD, KHÔI đã tặng cho TRÍ một tờ giấy xếp hạc kích thước \(n \times m\) (dọc \(n\) cm, ngang \(m\) cm).

TRÍ rất vui khi có phần quà này và hứa sẽ gấp ra \(1\) số con hạc giống hệt nhau mà không bỏ phí một mảnh giấy nào.

Tuy nhiên, TRÍ đang chuẩn bị cho kỳ thi kết thúc học phần cho nên TRÍ muốn gấp số con hạc là nhỏ nhất.

Biết rằng, để gấp một con hạc giấy bạn cần một mảnh giấy hình vuông. Và để xếp những con hạc giống nhau thì những hình vuông (chiều dài cạnh là số nguyên) đó cũng phải giống nhau, tất nhiên phải dùng kéo để cắt chúng ra.

Input

• Số nguyên dương \(t (t \leq 1000)\) - số test.
• Mỗi test chứa \(2\) số nguyên dương \(n, m(n, m \leq 1000)\)

Output

• Số con hạc phải gấp.

Example

2
2 2
6 9 

1
6