Підозрювані

У ході поліцейського розслідування було виявлено $n$ підозрюваних, і тепер свідки повинні спробувати ідентифікувати злочинця. Зріст кожного $i$-го підозрюваного був виміряний, але через неточність вимірювань відомо лише, що їх зріст є дійсним числом в інтервалі від $l_i$ до $r_i$ (включно). У найкращому випадку один з підозрюваних є злочинцем, але можливо, що жоден з них не є таким.

Одна розстановка полягає у виборі двох натуральних чисел $a$ і $b(1\le a\le b\le n)$, після чого підозрювані $a,a+1,...,b$ відводяться в окрему кімнату, щоб свідки могли спробувати впізнати злочинця. Оскільки свідки можуть бути збиті з пантелику, якщо двоє підозрюваних мають однаковий зріст, то розстановка допускається лише в тому випадку, якщо можна гарантувати, що жодні два підозрюваних не матимуть однаковий зріст. Під час розстановки свідки завжди зможуть впізнати злочинця, якщо він знаходиться серед вибраних підозрюваних, або скажуть, що його серед них немає.

Ведучий слідчий тепер зацікавлений у відповідях на наступні питання: "Якби я був впевнений, що злочинець знаходиться тільки між $p$ і $q(p\le q)$, то яка найменша кількість розстановок необхідна в гіршому випадку, щоб свідки змогли знайти злочинця або повідомити, що він не входить до числа підозрюваних?" Допоможіть ведучому слідчому відповісти на $q$ таких питань.

Вхідні дані

У першому рядку міститься одне натуральне число $n$ — кількість підозрюваних. Наступні $n$ рядків містять два натуральних числа $l_i$ і $r_i(1\le l_i\le r_i\le 10^9)$, що представляють можливий діапазон зросту підозрюваного номер $i$.

Наступний рядок містить натуральне число $q$ — кількість питань. Наступні $q$ рядків містять два натуральних числа $p_i$ і $q_i(1\le p_i\le q_i\le n)$, що визначають питання.

Вихідні дані

У $q$ рядках виведіть відповіді на відповідні питання: мінімально необхідну кількість розстановок.

Приклади