Từ Salvador Dalí với "The Persistence of Memory" (Sự dai dẳng của ký ức), Marcel Proust với "In Search of Lost Time" (Đi tìm thời gian đã mất), hay Thanh Thảo với "Thời gian trắng" đến Nguyễn Minh Châu với truyện ngắn "Chiếc đồng hồ cũ". Các tác giả lớn đều thường tìm đến thời gian và chiếc đồng hồ làm cảm hứng cho các tác phẩm của mình. Mỗi người đều mang đến cho người đọc một cái nhìn mới, một tình cảm mới hay một thông điệp mới về đề tài này.

Trong lúc ôn tập cho Kì thi Tuyển sinh 10 môn Ngữ Văn, Gấu đã nảy ra một ý tưởng khi nhìn thấy chiếc đồng hồ treo tường ở lớp: Gấu sẽ tự tìm ra cho mình một điều gì đó thú vị về chiếc đồng hồ. Sau một hồi quan sát, Gấu nhận ra tại một số thời điểm, kim giờ và kim phút của đồng hồ trùng nhau và khiến người ta tưởng như đồng hồ chỉ có đúng một kim. Ví dụ, vào lúc 12:00 hay khoảng 6:33, chiếc đồng hồ sẽ có tính chất này. Gấu gọi đây là những khoảnh khắc đặc biệt.

Từ đó, Gấu tự hỏi rằng từ bây giờ đến lúc tan học, sẽ có bao nhiêu khoảnh khắc đặc biệt? Các bạn hãy giúp Gấu trả lời câu hỏi này nhé! Biết rằng, thời điểm hiện tại và thời điểm Gấu tan học xảy ra trong cùng một ngày, và thời điểm Gấu tan học luôn xảy ra sau ít nhất ~1~ phút so với thời điểm hiện tại.

Yêu cầu: Cho biết thời gian hiện tại và thời điểm Gấu tan học, hãy cho biết số khoảnh khắc đặc biệt giữa hai thời điểm trên (tính cả hai thời điểm đó). Giả sử độ chia nhỏ nhất của đồng hồ là nhỏ đến mức không đáng kể, tức quỹ đạo chuyển động của các kim đồng hồ là một hình tròn liên tục.

Input

Nhập dữ liệu qua tập tin văn bản LITERATURE.INP:

• Dòng đầu tiên chứa một số nguyên ~T~ cho biết số lượng truy vấn.
• Trong ~T~ dòng tiếp theo, mỗi dòng chứa hai thời điểm được biểu diễn dưới dạng ~H:M~ với ~H, M~ lần lượt là giờ và phút của thời điểm tương ứng (~0 \leq H < 24~ và ~0 \leq M < 60~).

Output

Xuất dữ liệu qua tập tin văn bản LITERATURE.OUT:

• In ra ~T~ số nguyên theo thứ tự truy vấn là số khoảnh khắc đặc biệt giữa hai thời điểm nêu trên, tính cả hai thời điểm đó.

Ràng buộc

Ví dụ

Input mẫu 1

1
00:00 03:00

Output mẫu 1

3

Input mẫu 2

3
07:30 09:00
09:30 11:00
00:00 00:30

Output mẫu 2

2
2
1

Giải thích

• Ở ví dụ đầu tiên, khoảnh khắc đặc biệt là đúng ~00:00~, khoảng ~01:05~ và khoảng ~02:11~.
• Ở ví dụ thứ hai, số khoảnh khắc đặc biệt cho từng truy vấn là ~2, 2, 1~ do đó ta in ra đáp án theo thứ tự này.
• Sau đây là hình minh họa cho mặt đồng hồ vào khoảnh khắc ngay trước ~02:11~ một chút, cụ thể là vào lúc ~2~ giờ ~\frac{120}{11}~ phút:

Trong tiết toán vừa rồi, Gấu được học về các bài toán vận dụng tư duy logic để đếm số chữ số của một số nguyên cực kỳ lớn, ví dụ như đếm số chữ số ~0~ trong ~100!~. Rõ ràng, ta không thể viết ~100!~ ra để mà đếm số chữ số ~0~ được.

Lấy ý tưởng từ bài tập môn Toán, thầy giáo dạy Tin của Gấu cho Gấu một bài tập khác như sau:

• Cho hai số nguyên ~L, R~, thầy của Gấu lần lượt viết các số nguyên ~L^2, (L+1)^2, (L+2)^2, \dots, R^2~ liên tục từ trái sang phải lên bảng.
• Các số được viết tạo thành một số nguyên vô cùng lớn và nhiệm vụ của Gấu là phải đếm số chữ số của số nguyên trên bảng.

Yêu cầu: Cho hai số nguyên ~L, R~, hãy thực hiện yêu cầu của thầy giáo dạy Tin của Gấu.

Input

Nhập dữ liệu qua tập tin văn bản MATHEMATICS.INP:

• Dòng đầu tiên chứa một số nguyên ~T~ cho biết số lượng truy vấn.
• Trong ~T~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~L, R~ mô tả yêu cầu của thầy giáo.

Output

Xuất dữ liệu qua tập tin văn bản MATHEMATICS.OUT:

• In ra ~T~ số nguyên theo thứ tự truy vấn là số lượng chữ số ở mỗi yêu cầu của thầy giáo.

Ràng buộc

Ví dụ

Input mẫu

2
1 4
5 9

Output mẫu

5
10

Giải thích

• Ở truy vấn đầu tiên, số mà thầy giáo viết lên bảng là ~14916~, có ~5~ chữ số.
• Ở truy vấn thứ hai, số mà thầy giáo viết lên bảng là ~2536496481~, có ~10~ chữ số.

"Two Goats, frisking gayly on the rocky steeps of a mountain valley, chanced to meet, one on each side of a deep chasm through which poured a mighty mountain torrent. The trunk of a fallen tree formed the only means of crossing the chasm, and on this not even two squirrels could have passed each other in safety. The narrow path would have made the bravest tremble. Not so our Goats. Their pride would not permit either to stand aside for the other.

One set her foot on the log. The other did likewise. In the middle they met horn to horn. Neither would give way, and so they both fell, to be swept away by the roaring torrent below."

"The two goats story", Aesop's Fables (source: https://fablesofaesop.com/two-goats.html)

Mẫu truyện trên kể về hai chú dê cùng đi qua một chiếc cầu chật hẹp được hình thành từ một cái thân cây đã ngã. Với lòng tự tôn vô cùng to lớn, không một con dê nào chịu nhường con còn lại. Kết quả thì hẵn chúng ta ai cũng đã biết: chúng dùng sừng húc nhau trên cây cầu chênh vênh, khiến cả hai cùng ngả xuống dòng sông đang chảy siết.

Tuy nhiên, hôm nay, chúng ta sẽ hình dung lại câu truyện trên theo một cách hòa thuận và cho nó một cái kết có hậu hơn. Cụ thể, hai chú dê quyết định sử dụng phép thuật để xây một chiếc cầu cho cả hai cùng đi qua.

Nếu hình dung khoảng không gian giữa hai vách núi thành một bảng hai chiều có ~n~ dòng và ~m~ cột, với cột thứ ~1~ và thứ ~m~ là hai vách núi, ta có bảng ~a~ kích thước ~n \times m~ sao cho ~a_{i, j}~ mô tả chi phí xây dựng cầu tại vị trí giao giữa dòng thứ ~i~ và cột thứ ~j~. Nhiệm vụ của hai chú dê là như sau:

• Chọn ra ~k~ dòng liên tiếp làm vùng xây cầu.
• Chọn một dòng bất kỳ rồi dùng phép thuật để gán toàn bộ các giá trị ~a_{i, j}~ trên dòng đó bằng ~0~.
• Với mỗi dòng ~i~ trong số các dòng đã được chọn, hai chú dê cần kết nối hai vách núi như sau: Chọn một tập các ô trên dòng ~i~ sao cho ô ~(i, 1)~ và ~(i, m)~ luôn được chọn, hơn nữa, hai ô liên tiếp (chỉ tính trên dòng ~i~) cách nhau không quá ~d~ ô. Ví dụ, giả sử hai chú dê chọn các cột ~j_1, j_2, j_3, \dots, j_r~ trên dòng ~i~ để xây cầu, ta cần đảm bảo ~j_1 = 1, j_r = m~ và:

$$ \max_{2 \leq i \leq r} j_i - j_{i-1} \leq d $$

Trong các cách chọn ô để xây cầu thỏa mãn cả ~3~ điều kiện trên, hãy giúp hai chú dê chọn ra các xây cầu có tổng chi phí nhỏ nhất.

Input

Nhập dữ liệu qua tập tin văn bản ENGLISH.INP:

• Dòng đầu tiên của dữ liệu vào chứa bốn số nguyên ~n, m, k, d~ (với ~k \leq n~ và ~d \leq m~) lần lượt là kích thước của khoảng không gian cần xét giữa hai vách núi, số dòng cần chọn và khoảng cách tối đa giữa hai ô trên cùng một dòng.
• Trên ~n~ dòng tiếp theo, mỗi dòng chứa ~m~ số nguyên ~a_{i, 1}, a_{i, 2}, a_{i, 3}, \dots, a_{i, m}~ mô tả chi phí xây cầu cho các ô trên bảng.

Output

Xuất dữ liệu qua tập tin văn bản ENGLISH.OUT:

• In ra một số nguyên duy nhất là tổng chi phí nhỏ nhất để xây cầu.

Ràng buộc

Ví dụ

Input mẫu

4 4 3 2
4 1 3 2 
4 3 3 5 
3 4 3 2 
2 3 1 5 

Output mẫu

15

Giải thích

• Đầu tiên, ta chọn dòng ~1, 2, 3~ để xây cầu.
• Sau đó, dùng phép thuật để gán toàn bộ các giá trị trên dòng thứ hai thành ~0~.
• Cuối cùng, ta chọn các ô như sau:
  • Ở dòng đầu tiên: Chọn các ô ~(1, 1)~, ~(1, 2)~ và ~(1, 4)~ với chi phí ~4 + 1 + 2 = 7~.
  • Ở dòng thứ hai: Chọn các ô ~(2, 1)~, ~(2, 2)~ và ~(2, 4)~ với chi phí ~0~ do đã sử dụng phép thuật.
  • Ở dòng thứ ba: Chọn các ô ~(3, 1)~, ~(3, 3)~ và ~(3, 4)~ với chi phí ~3 + 3 + 2 = 8~.
• Tổng chi phí cuối cùng là ~15~, có thể thấy, đây là phương án tối ưu.