Cho tờ giấy hình chữ nhật có kích thước ~a \times b~ ~(a > b)~. tahp 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ì tahp sẽ có một mảnh giấy hình vuông kích thước ~b~ x ~b~ và một mảnh kích thước ~b \times (a - b)~. tahp 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 số lần tahp cần cắt để các mảnh giấy trở thành hình vuông.

Input

• Dòng đầu tiên ~t~ số lượng test case ~(1 \le t \le 100)~.
• Gồm ~t~ dòng mỗi dòng chứa hai số nguyên ~a~ và ~b~ ~(1 \le a, b \le 10^{9})~, cách bởi ~1~ dấu cách.

Output

• Ghi ra số lần cắt.

Sample Input

1
10 7

Sample Output

5

Subtask

• ~50\%~ số test có ~t \le 10~ và ~(1 \le a, b \le 10^{6})~
• Số test còn lại không có điều kiện gì thêm.

Note

Ta có ~a~, ~b~ ~(a > b)~ là độ dài các cạnh của hình có diện tích bé nhất sau mỗi lần cắt.

Ta có: ~a = 10~, ~b = 7~

• Lần cắt thứ ~1~ : ~a~ = ~7~, ~b~ = ~3~.
• Lần cắt thứ ~2~ : ~a~ = ~4~, ~b~ = ~3~.
• Lần cắt thứ ~3~ : ~a~ = ~3~, ~b~ = ~1~.
• Lần cắt thứ ~4~ : ~a~ = ~2~, ~b~ = ~1~.
• Lần cắt thứ ~5~ : ~a~ = ~1~, ~b~ = ~1~.

Vậy sau ~5~ lần cắt các mảnh giấy đều thành hình vuông.