Vinh và Tuấn đều rất yêu thích series Project SEKAI, nên cả hai quyết định lên Hà Nội để xem bộ phim "Colorful Stage! The Movie: A Miku Who Can't Sing" tại rạp chiếu phim ở Hà Nội.

Vinh sẽ có mặt ở Hà Nội từ thời điểm ~a~ đến thời điểm ~b~ (tính cả hai ngày).

Tuấn cũng sẽ có mặt ở Hà Nội từ thời điểm ~c~ đến thời điểm ~d~ (tính cả hai ngày).

Yêu cầu: Hãy tính xem có bao nhiêu ngày mà cả Vinh và Tuấn cùng ở Hà Nội, tức là số ngày giao nhau trong hai khoảng thời gian.

Dưới đây là số ngày trong mỗi tháng:

Input

~4~ xâu ~a, b, c, d~ được ghi trên ~4~ dòng riêng biệt

Mỗi chuỗi ngày ~(a, b, c, d)~ là chuỗi gồm đúng ~5~ ký tự, theo định dạng MM-DD

MM là tháng, thuộc tập ~\{01, 02, ..., 12\}~.

DD là ngày hợp lệ của tháng MM, xét trong năm không nhuận (tức là tháng ~2~ có tối đa ~28~ ngày).

Đảm bảo rằng ~a \le b~ và ~c \le d~ theo thứ tự thời gian.

Output

Một số nguyên duy nhất — số ngày mà Vinh và Tuấn cùng có mặt ở Hà Nội.

Subtask

Sample Input

08-10
08-21
08-15
08-20

Sample Output

6

Gamer Alex đang chơi một game RPG có bản đồ dungeon dạng lưới ~n \times m~. Mỗi ô chứa một monster với điểm sức mạnh là số nguyên dương. Nhân vật của Alex có skill đặc biệt L-Strike Combo với quy tắc:

• Chỉ có thể di chuyển theo một hướng (ngang hoặc dọc) ban đầu
• Nếu có rẽ, sau khi rẽ thì đường đi sẽ chỉ được đi theo chiều sau khi rẽ.
• Chỉ được rẽ một lần duy nhất
• Không được quay lại ô đã đi qua.

Ví dụ:

• Một đường đi chỉ đi thẳng ngang hoặc thẳng dọc là hợp lệ.

• Một đường đi ngang rồi rẽ dọc, hoặc đi dọc rồi rẽ ngang cũng hợp lệ.

• Một đường đi có hai lần rẽ hoặc quay lại ô cũ là không hợp lệ.

Combo cho phép người chơi chọn bất kì một nơi bắt đầu và nơi kết thúc, miễn ta có thể đi từ nơi bắt đầu đến nơi kết thúc một cách hợp lệ theo quy tắc của skill. Điểm Damage được tính bằng tích điểm sức mạnh của tất cả monster trên đường đi.

Alex rất thích số ~0~ vì nó tượng trưng cho sự hoàn hảo và cân bằng, do đó Alex muốn tìm combo có số chữ số ~0~ tận cùng nhiều nhất trong điểm Damage để khoe với bạn bè.

Yêu cầu: Cho bản đồ dungeon, hãy tìm số lượng chữ số ~0~ tận cùng lớn nhất có thể có trong điểm Damage của một skil L-Strike combo để Alex có thể khoe với bạn bè.

Input

Dòng đầu tiên chứa ~2~ số nguyên dương ~n, m~ ~(1 \le n, m \le 10^3)~

~n~ dòng tiếp theo, mỗi dòng gồm ~m~ số nguyên dương ~a_{i,j}~ ~(1 \le a_{i,j} \le 10^3)~

Output

Một dòng duy nhất là số lượng số ~0~ lớn nhất trong damage của một skill L-Strike combo có thể có

Subtask

Sample Input 1

2 2
5 2
4 3

Sample Output 1

1

Sample Input 2

5 5
29 13 5 7 120
1 1 60 21 19
1 1 3 2 21
20 11 4 5 6
22 8 9 2 3

Sample Output 2

3

Giải thích

• Ở ví dụ đầu:

• Ở ví dụ thứ 2:

Một số được gọi là số đối xứng nếu như ta viết số đó từ trái sang phải hay từ phải sang trái đều nhận kết quả giống nhau. Ví dụ: ~121, 151, 123321~ là những số đối xứng.

Thế nhưng, Alice lại thấy tính chất số kia quá nhàm chán nên quyết định chế ra định nghĩa mới về những con số.

Một số được định nghĩa là một số siêu đối xứng nếu như tồn tại ít nhất một cách khi thêm một chữ số bất kì vào sau số đó, chúng trở thành thành số đối xứng. Ví dụ: ~21, 322, 55~ là những con số siêu đối xứng theo định nghĩa của Alice.

Cô ấy thắc mắc, trong các đoạn ~[l, r]~ cho trước, có bao nhiêu số là số siêu đối xứng?

INPUT

• Dòng đầu tiên chứa số nguyên dương ~t~ (~1 \le t \le 5000~) là số bộ test.
• ~t~ dòng tiếp theo, mỗi dòng gồm ~2~ số nguyên dương ~l, r~ (~1 \le l \le r \le 10^{18}~) mô tả một test.

OUTPUT

• Với mỗi test, hãy in ra kết quả bài toán trên một dòng.

SUBTASKS

SAMPLE INPUT

3
1 99
220 550
1000 2000

SAMPLE OUTPUT

99
33
101

Một dãy số ~a_1, a_2, ..., a_n~ (~n \ge 4~) được gọi là dãy đặc biệt nếu đồng thời thỏa mãn hai điều kiện sau:

• ~n~ chẵn.
• ~a_1 + a_n > a_2 + a_{n-1}~ ~> ... > a_{\frac{n}{2}} + a_{\frac{n}{2} + 1}~.

Yêu cầu: Cho dãy số gồm ~m~ phần tử, bao gồm các số ~a_1, a_2, ..., a_m~ (~4 \le m \le 350~). Nhiệm vụ của bạn là hãy đếm số lượng dãy con đã cho thỏa mãn dãy đặc biệt theo định nghĩa trên. Biết rằng, ~a_{i_1}, a_{i_2}, ..., a_{i_k}~ là một dãy con nếu tồn tại dãy chỉ số ~i_1 < i_2 < ... i_k~ với (~i_1, i_2..., i_k \in [1; m]~).

INPUT

Dòng đầu tiên chứa số nguyên dương ~m~ (~4 \le m \le 350~).

Dòng tiếp theo chứa ~m~ số nguyên dương ~a_i~ (~1 \le a_i \le 500~).

OUTPUT

In ra số nguyên duy nhất là số lượng dãy con đặc biệt khi chia dư cho ~10^9 + 9~.

SAMPLE INPUT

6
1 8 4 9 7 5

SAMPLE OUTPUT

2

Có hai dãy đặc biệt là ~{8, 4, 9, 7}~ và ~{8, 4, 7, 5}~.

SUBTASKS

Trong một buổi tối, cô bé ~Lona~ nảy ra một ý tưởng thú vị khi đang nhìn vào một bảng nhị phân trên giấy: "Điều gì sẽ xảy ra nếu mình có thể biến bảng này thành một bảng khác, gần giống thôi, bằng những thao tác đơn giản?"

Cho hai bảng nhị phân ~A~ và ~B~ có kích thước ~n \times n~. Mỗi ô của bảng chứa giá trị ~0~ hoặc ~1~. Cô bé Lona có thể thực hiện hai loại thao tác sau để biến đổi bảng ~A~:

1. Hoán đổi hai cột liền kề:
   Thao tác 1 c sẽ đổi chỗ cột thứ ~c~ và cột thứ ~c+1~ của bảng ~A~.
2. Đảo giá trị cả hàng:
   Thao tác 2 r sẽ đảo tất cả giá trị trên hàng thứ ~r~ (0 thành 1 và 1 thành 0).

Lona muốn biến bảng ~A~ thành một bảng ~C~ sao cho ~C~ khác bảng ~B~ không quá 1 ô.

Nhiệm vụ của bạn là tìm số thao tác ít nhất để thực hiện điều đó. Nếu không thể đạt được mục tiêu, hãy in ra ~-1~.

INPUT

• Dòng đầu tiên chứa số nguyên dương ~n~ — kích thước bảng. (~1 \le n \le 100~)
• ~n~ dòng tiếp theo, mỗi dòng gồm ~n~ số nguyên ~0~ hoặc ~1~ — mô tả bảng ~A~.
• ~n~ dòng tiếp theo, mỗi dòng gồm ~n~ số nguyên ~0~ hoặc ~1~ — mô tả bảng ~B~.

OUTPUT

• Nếu không có cách nào để biến bảng ~A~ thành bảng ~C~ sao cho bảng ~C~ khác bảng ~B~ không quá một ô, in ra -1.
• Ngược lại, in ra số nguyên ~s~ là số thao tác cần thực hiện.
• ~s~ dòng tiếp theo, mỗi dòng gồm hai số nguyên ~t~ và ~x~:
  • Nếu ~t = 1~, thao tác đổi chỗ cột ~x~ và ~x+1~.
  • Nếu ~t = 2~, thao tác đảo toàn bộ hàng ~x~.

SAMPLE INPUT 1

3
0 0 1
1 0 0
0 0 1
1 0 0
0 0 1
1 0 0

SAMPLE OUTPUT 1

3
1 2
1 1
1 2

SAMPLE INPUT 2

7
1 0 1 1 0 0 0
0 1 0 1 1 0 0
1 1 1 0 0 1 1
1 0 1 0 1 1 1
1 1 1 0 1 0 1
0 0 0 1 0 1 1
1 1 0 0 1 0 0
0 0 0 0 1 1 1
1 1 0 0 1 0 0
1 0 1 1 0 1 1
0 1 1 1 0 1 1
1 1 1 0 0 1 1
0 0 1 1 1 0 0
1 1 0 0 0 0 1

SAMPLE OUTPUT 2

14
1 1
1 4
1 3
1 2
1 6
1 5
1 4
1 3
1 6
1 5
1 4
1 6
1 5
1 6

SUBTASKS

Trong một tuần lễ được nghỉ học, cô bé ~Lona~ đam mê Toán học và giải thuật, quyết định không dành thời gian để lướt mạng xã hội hay chơi game như bao bạn bè cùng trang lứa. Thay vào đó, cô mở máy tính lên, mở trình soạn thảo quen thuộc, và bắt đầu… sáng tạo bài toán của riêng mình.

Cho ~n~ điểm trên mặt phẳng, khoảng cách giữa hai điểm ~A(x, y)~ và ~B(x', y')~ được xác định bằng công thức: ~dist(A, B) = |x - x'| + |y - y'|~.

Nhiệm vụ của bạn là giúp ~Lona~ đếm số bộ ba điểm (~x, y, z~) thỏa mãn điều kiện sau: ~dist(x, y) = dist(y, z) = dist(x, z) = mindist(x) = mindist(y) = mindist(z)~

Trong đó, ~mindist(A)~ là khoảng cách ngắn nhất đi từ một điểm thuộc ~n-1~ điểm còn lại đến điểm ~A~.

Hãy giúp cô ấy tìm ra số bộ ba điểm thỏa mãn điều kiện trên!

INPUT

• Dòng đầu tiên gồm số nguyên ~n~ — số điểm trên mặt phẳng. (~1 \le n \le 10^5~)
• ~n~ dòng tiếp theo, mỗi dòng gồm hai số nguyên dương ~x, y~ — tọa độ các điểm trên mặt phẳng. (~1 \le x, y \le 10^9~)

OUTPUT

• In ra một số nguyên duy nhất là số bộ ba cần tìm.

SAMPLE INPUT

5
1 1
3 1
1 3
2 2
4 2

SAMPLE OUTPUT

3

SUBTASKS