CUT 1

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
dang7rickroll
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Clang, Clang++, Cobol, D, Groovy, Haskell, JS, Lua, Node JS, ObjectiveC, OCaml, Output, Pascal, PHP, Prolog, Python, Ruby, Rust, Scala, Swift
Điểm: 150 Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

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

Test 1

Input 
1
10 7
Output 
6

Bình luận