TaThanHungBC là một cậu bé rất thông minh và tinh nghịch. Hôm nay cậu được mẹ mua cho một mảnh giấy màu có kích thước ~n \times m~.

Là một người nghệ sĩ thực thụ, TaThanHungBC luôn hướng tới sự hoàn hảo, cụ thể cậu định nghĩa một mảnh giấy ~x \times y~ là hoàn hảo nếu như ~\frac{x+y}{2} = \sqrt{x \times y}~.

TaThanHungBC có thể dùng kéo để cắt một mảnh giấy ra thành hai mảnh giấy khác. TaThanHungBC muốn sao cho sau khi hoàn thành cắt thì mọi mảnh giấy đều là hoàn hảo. Tuy nhiên do quá bạn chơi Genshin nên TaThanHungBC muốn cắt ít lần nhất có thể. Bạn hãy giúp TaThanHungBC tìm ra số lần cắt ít nhất có thể.

Tuy nhiên, TaThanHungBC không biết kích thước chính xác kích thước của mảnh giấy mẹ mua cho cậu. Nên cậu sẽ đặt ra cho bạn ~T~ giả định, giải định thứ ~i~ hỏi xem nếu mẹ cậu mua mảnh giấy kích thước ~n_i \times m_i~ thì cậu sẽ cần cắt ít nhất bao lần?

Input

• Dòng đầu tiên chứa số nguyên dương ~T~ là số giả định.
• ~T~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương ~n, m~ tương ứng với một giả định.

Output

• Đưa ra ~T~ dòng, dòng thứ ~i~ tương ứng với đáp án của giả định thứ ~i~.

Constraint

• ~T \le \mathord{?} \mathord{?} \mathord{?}~
• ~n_i, m_i \leq 500~ ~\forall 1 \leq i \leq T~

Subtask

• Subtask 1 (10%): ~T = 1~, ~n, m \leq 20~.
• Subtask 2 (20%): ~T = 1~, ~n, m \leq 500~.
• Subtask 3 (30%): ~n, m \leq 20~.
• Subtask 4 (40%): không có giới hạn gì thêm.

Sample Input

2
3 5
3 3

Sample Output

3
0

Note

Cách cắt của giả định ~1~.