Di chuyển trong hình chữ nhật (Bản khó)

View as PDF

Submit solution


Points: 200 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Authors:
Problem type

Sau khi hú vía mới qua được cảnh ngàn cân treo sợi tóc ấy, Tấn đã thành công đưa team chiếm giải kk và mới được ba tặng con Robot siêu cấp có cục pin siêu khủng. Tấn hằng ngày vẫn lấy nó ra chơi. Cho đến 1 ngày, Tấn đọc được bài viết về Tỉ Lệ Vàng, Tấn mới nghĩ ra một trò chơi mới.

Tấn lôi cái bàn cờ vô hạn của mình ra, và đánh dấu T khu vực hình chữ nhật, khu thứ i2 cạnh lần lượt là X_iY_i. Với mỗi khu thứ i, Tấn đặt con Robot lên ô trái trên của khu vực ấy, đặt 1 cây bút màu mà cậu dùng để đánh dấu khu vực xuống phía dưới con Robot cho nó vạch đường đi, rồi chơi như sau: Hướng góc nhìn của cả con Robot về hướng bên tay phải, rồi cho nó di chuyển liên tục. Nếu như ô nó dự định đi tới (hoặc 1 cạnh kề ô đó) bị vẽ màu thì nó sẽ dừng lại, nó sẽ quay 90^o về phía tay phải (so với góc nhìn của con robot) rồi đi tiếp. Cho đến 1 ô nào đó mà nó quay đủ 360^o mà không thể tìm thấy đường đi hợp lệ thì nó sẽ dừng lại và báo hiệu cho Tấn biết số hiệu của ô nó dừng lại:

Các ô được đánh số như thế này trong khu vực 8x8. Robot sẽ từ ô số 1 qua ô số 8 (hàng số màu cam), rồi từ đó đi đến ô số 64 (hàng số màu xanh nhạt), rồi từ đó đi tiếp đến ô 57 (hàng số màu tím), rồi tới ô số 9 (hàng số màu xanh đậm), rồi tiếp tục quay rồi đi tiếp tới ô 15 (hàng số màu hường), rồi đi tiếp… cho đến ô số 36 (ô in đậm) thì Robot không tìm thấy đường đi nên nó sẽ dừng.

Cậu ghi lại ô dừng của Robot trong T trường hợp, rồi đem cho Tài xem. Mỗi tội sau đó Tấn lại lỡ tay làm rách tờ giấy nên kết quả cậu ghi lại đều bị mất hết, may thay vẫn còn các giá trị X_iY_i của T khu vực ấy, nên ít nhất cậu cũng hy vọng có thể khôi phục lại kết quả. Các bạn ơi, hãy giúp Tấn tìm ra các kết quả bị mất nhé!

Input:

  • Dòng 1 gồm số T≤10^6;
  • T dòng sau, mỗi dòng thứ i2 số X_iY_i X_i,Y_i≤10^8.

Output:

  • Với mỗi dòng thứ i, in ra theo đề yêu cầu (kèm chữ “Test #” với chỉ số của câu hỏi (i).

Scoring:

  • 20% số test có X_i,Y_i ≤ 10^2.
  • 50% số test có X_i,Y_i ≤ 10^5.

Example

Test 1

Input

1
8 8

Output

Test #1: 36

Note
  • Hình ở trên :))))

Comments

There are no comments at the moment.