Cho tờ giấy hình chữ nhật có kích thước \(a \times b\) \((a > b)\) . JK sau đó gấp chéo tờ giấy tạo thành đường gấp có góc 45 độ, một mép trùng với một cạnh của tờ giấy, sau đó cắt phần giấy thừa không bị gấp đè lên đi. Sau khi cắt thì JK sẽ có một mảnh giấy hình vuông kích thước \(b \times b\) và một mảnh kích thước \(b \times (a-b)\). JK lại tiếp tục thực hiện thao tác như trên với mảnh giấy \(b \times (a - b)\) cho đến khi tất cả mảnh giấy đều là hình vuông.

Yêu cầu: Hãy xác định xem JK có thể gấp được bao nhiêu hình vuông.

Input

• Dòng 1: \(t\) \((t \le 100)\) - số test
• \(t\) dòng tiếp: \(a\) \(b\) \((b < a \le 10^9)\)

Output

• \(t\) dòng, đáp án đề bài

Example

1
10 7

6