Năm nay, dịch covid-19 diễn ra khá phức tạp ở nước ta, nhiều trường học các em học sinh không được đến trường. Trong tình hình ấy, Bộ Giáo Dục đã định hướng việc học và dạy học trực tuyến trên cả nước áp dụng cho các tỉnh thành thuộc vùng đỏ. Do nhu cầu học trực tuyến của các em học sinh dẫn đến giá thành của các máy tính xách tay (laptop) tăng phi mã, gây khó khăn rất nhiều cho các bậc phụ huynh khi muốn mua một chiếc laptop cho con em mình.

Bác phụ huynh XYZ muốn mua cho con mình một chiếc laptop, bác tham khảo ý kiến của một số các chuyên gia về máy tính và được những câu trả lời như sau:

• Chuyên gia thứ nhất: máy tính \(i\) tốt hơn máy tính \(j\) khi giá thành của máy tính \(i\) cao hơn máy tính \(j\).
• Chuyên gia thứ hai: máy tính \(i\) tốt hơn máy tính \(j\) khi hiệu suất của máy tính \(j\) cao hơn máy tính \(j\).
• Chuyên gia thứ ba: máy tính \(i\) tốt hơn máy tính \(j\) khi mà giá của máy tính \(i\) thấp hơn máy tính \(j\) nhưng hiệu suất của máy tính \(i\) lại cao hơn máy tín \(j\).

Cho rằng ý kiến của chuyên gia thứ ba là hợp lý, phụ huynh XYZ quyết định sẽ tìm mua chiếc laptop như ý kiến của chuyên gia này.
Bác hỏi \(n\) cửa hàng bán máy tính, cửa hàng thứ \(i\) tư vấn nên mua máy tính có giá là \(a[i]\) và hiệu suất là \(b[i]\).

👉 Yêu cầu: Hãy cho biết, bác phụ huynh XYZ có thể có bao nhiêu lựa chọn cho việc mua máy tính của mình (dựa trên ý kiến tham khảo của chuyên gia thứ ba).

Input: LAPTOP.INP

• Dòng 1: chứa số nguyên dương \(n\) \((1 ≤ n \le10^5)\) – số lượng cửa hàng máy tính.
• \(n\) dòng tiếp theo: dòng thứ \(i\) chứa hai số nguyên dương là \(a[i], b[i] (1≤a[i], b[i] ≤ 10^9)\) – giá thành và hiệu suất của máy tính thứ \(i\).

Output: LAPTOP.OUT

• Chứa một số nguyên duy nhất là số lượng máy tính đáp ứng yêu cầu của phụ huynh XYZ (theo quan điểm của chuyên gia thứ 3).

Ví dụ:

Input (LAPTOP.INP)

5
3 5
1 2
4 3
6 9
2 1

Output (LAPTOP.OUT)

2

Giải thích ví dụ:

• Máy tính thứ nhất có giá thấp hơn máy tính thứ ba, nhưng hiệu suất lại cao hơn máy tính thứ ba.
• Máy tính thứ hai có giá thấp hơn máy tính thứ năm, nhưng hiệu suất lại cao hơn máy tính thứ năm.

👉 Vậy, hai máy tính mà phụ huynh XYZ có thể lựa chọn là máy tính thứ nhất và thứ hai.

Ràng buộc:

• Subtask 1: 60% test đầu tiên ứng với \(1 \le n\le10^3\).
• Subtask 2: 40% test còn lại không có ràng buộc gì.

Cho dãy số nguyên \(A = (a_1, a_2, \ldots, a_n) (1 \le n \le 10^5;-10^6 \le a_i \le 10^6, \forall i \in [1, n]) \). Hãy tìm một đoạn dài nhất gồm các phần tử liên tiếp trong dãy \(A: (a_L, a_{L+1}, \ldots, a_H)\) sao cho tổng bằng \(0\).

Dữ liệu vào

Đọc từ file SZERO.INP:

• Dòng 1: Chứa số \(n\),
• Dòng 2: Chứa \(n\) số \(a_1, a_2, \ldots, a_n\) theo đúng thứ tự cách nhau ít nhất một dấu cách.

Kết quả

Ghi ra file SZERO.OUT:

• Một dòng duy nhất ghi hai số nguyên \(L, H\) cách nhau ít nhất một dấu cách.
• Đoạn \([L, H]\) là đoạn dài nhất có tổng bằng \(0\).

Ví dụ

SZERO.INP

9
2 7 5 -3 -2 4 -9 -2 1

SZERO.OUT

2 8

Ghi chú

Dữ liệu vào luôn được đảm bảo hợp lệ, tức là luôn tồn tại ít nhất một đoạn con liên tiếp có tổng bằng \(0\).

Ràng buộc

• Subtask 1: \(30\%\) số test, \(1 \le n \le 500\),
• Subtask 2: \(30\%\) số test, \(501 \le n \le 5000\),
• Subtask 3: \(20\%\) số test, \(5001 \le n \le 10^5\),
• Subtask 4: \(20\%\) số test, \(10^5 < n \le 10^6, -1 \le a[i] \le 1\).

Hai người chơi một trò chơi. Ban đầu người 1 chọn số nguyên dương ~n~ và đưa cho người 2. Người 2 thực hiện lặp lại các bước:

• Chọn một số nguyên dương ~x > 1~ sao cho ~n~ chia hết cho ~x~.
• Thay ~n~ bằng ~n / x~.

Khi ~n = 1~ và không còn nước đi hợp lệ, trò chơi kết thúc. Điểm của người chơi là số lần đã thực hiện bước trên.

Để tăng phần thú vị, người 1 chọn ~n~ có dạng ~\frac{a!}{b!}~ với ~a, b~ là số nguyên dương và ~a ≥ b~. Ở đây ~k!~ là tích của các số nguyên dương không vượt quá ~k~.

Yêu cầu: Với mỗi cặp ~(a, b)~, hãy tính số điểm tối đa có thể đạt được.

Input ~divgame.inp~

• Dòng 1: số nguyên dương ~t~ — số test ~(1 ≤ t ≤ 10^6)~.
• ~t~ dòng tiếp theo: mỗi dòng chứa cặp ~a, b~ ~(1 ≤ b ≤ a ≤ 5·10^6)~, biểu diễn ~n = \frac{a!}{b!}~.

Output ~divgame.out~

• Gồm ~t~ dòng, mỗi dòng in ra số điểm tối đa tương ứng test đó.

Ví dụ

divgame.inp

2
3 1
6 3

divgame.out

2
5

Giải thích:

• Với ~(a, b) = (3, 1)~: ~n = \frac{3!}{1!} = 6 = 2 · 3~. Có thể chia lần lượt cho ~2~, rồi ~3~ → tối đa 2 bước.
• Với ~(6, 3)~: ~n = \frac{6!}{3!} = 4 · 5 · 6 = 120 = 2^3·3·5~, tổng mũ nguyên tố là ~3 + 1 + 1 = 5~ → 5 bước.

Ràng buộc chấm điểm

• Subtask 1 (30%): ~1 ≤ b ≤ a ≤ 15~,
• Subtask 2 (30%): ~t = 1~,
• Subtask 3 (20%): ~1 ≤ b ≤ a ≤ 10^5~,
• Subtask 4 (20%): không ràng buộc thêm.

Phú ông có ~n~ con bò, mỗi con được gán một chỉ số id từ ~1~ đến ~n~. Con bò có chỉ số ~id~ mang mã giống ~a[id]~. Ban đầu, các con bò xếp theo thứ tự từ ~id = 1~ đến ~id = n~. Phú ông muốn chụp một bức ảnh gồm một số con bò liên tiếp để gửi tham dự cuộc thi Hoa hậu bò. Trước khi chụp ảnh, ông thực hiện ~m~ lần đổi chỗ các con bò theo các thao tác:

A i j: con bò có chỉ số id = ~i~ được chuyển sang đứng bên trái con bò có id = ~j~.

B i j: con bò có chỉ số id = ~i~ được chuyển sang đứng bên phải con bò có id = ~j~.

Sau khi thực hiện đủ ~m~ lượt đổi chỗ, ông muốn tìm một đoạn liên tiếp từ vị trí ~L~ đến ~R~ sao cho trong đoạn này, mỗi mã giống xuất hiện ít nhất một lần.

Chi phí của bức ảnh = ~R - L + 1~ (độ rộng của đoạn).
Yêu cầu: Tìm chi phí nhỏ nhất.

Dữ liệu vào (CPHOTO.INP)

Dòng 1: hai số nguyên ~n, m~ ~(1 ≤ n, m ≤ 10^5)~

Dòng 2: ~n~ số nguyên ~a_1, a_2, …, a_n~ ~(1 ≤ a_i ≤ 10^5)~

~m~ dòng tiếp theo: mỗi dòng mô tả phép đổi với định dạng ~A~ ~i~ ~j~ hoặc ~B~ ~i~ ~j~ ~(1 ≤ i, j ≤ n) ~

Kết quả ra (CPHOTO.OUT)

Một số nguyên duy nhất — chi phí nhỏ nhất tìm được.

Ví dụ:

CPHOTO.INP

6 3
1 4 1 2 4 1
A 1 3
B 4 2
B 6 1

CPHOTO.OUT

3

Giải thích:

Sau khi đổi, dãy mã giống cuối cùng: ~4 2 1 1 1 4~.
Đoạn ngắn nhất chứa đủ các giống là ~4 2 1~ (hoặc ~2 1 1 1 4~) có độ dài ~3~.

Ràng buộc chấm điểm

Subtask 1 (40%): ~m = 1~,

Subtask 2 (30%): ~1 ≤ n, m ≤ 1000~,

Subtask 3 (30%): không có ràng buộc thêm.