Trong một cuộc điều tra, đã xác định được ~n~ nghi phạm, công an đề nghị các nhân chứng tìm ra thủ phạm. Chiều cao của mỗi nghi phạm ~i~ là một số thực trong khoảng từ ~l_i~ đến ~r_i~. Có thể có ít nhất một nghi phạm là thủ phạm, nhưng cũng có thể không có nghi phạm nào.

Một cuộc đối chiếu gồm việc chọn hai số nguyên dương ~a~ và ~b~ (~1 \le a \le b \le n~), sau đó đưa các nghi phạm từ ~a, a + 1, \dots, b~ vào một phòng riêng để các nhân chứng có thể cố gắng nhận diện thủ phạm. Do những người làm chứng có thể bị nhầm lẫn nếu hai nghi phạm có chiều cao giống nhau, nên trong một cuộc đối chiếu không có hai nghi phạm nào có chiều cao giống nhau.

Điều tra viên trưởng hiện đang quan tâm đến việc trả lời các câu hỏi sau: "Nếu nhãn của thủ phạm chỉ có thể nằm trong khoảng từ ~p~ đến ~q~ (~p \le q~), thì số lượng cuộc đối chiếu tối thiểu là bao nhiêu để nhân chứng có thể tìm ra thủ phạm trong trường hợp xấu nhất?" Hãy giúp điều tra viên trưởng trả lời ~q~ câu hỏi như vậy.

Yêu cầu: Hãy tìm số lượng cuộc đối chiếu tối thiểu cho mỗi câu hỏi.

Input

• Dòng đầu tiên chứa một số nguyên dương ~n~, số lượng nghi phạm.
• ~n~ dòng tiếp theo chứa hai số nguyên dương ~l_i~ và ~r_i~ (~1 \le l_i < r_i \le 10^9~), đại diện cho khoảng chiều cao có thể có của nghi phạm có thứ ~i~.
• Dòng tiếp theo chứa một số nguyên dương ~q~ là số lượng câu hỏi.
• ~q~ dòng tiếp theo chứa hai số nguyên dương ~p_i~ và ~q_i~ (~1 \le p_i \le q_i \le n~) là một câu hỏi.

Output

• In ra ~q~ dòng, mỗi dòng là câu trả lời cho câu hỏi tương ứng: số lượng cuộc đối chiếu tối thiểu.