В процессе подготовки организаторы Закрытой олимпиады школьников по программированию решили украсить аудиторию. Для этого на стене на одной прямой было вбито $2n$ колышков. Все колышки находятся в различных позициях. Между ними было натянуто $n$ ниточек, $i$-я из них была протянута между колышками на расстоянии $l_i$ и $r_i$ от начала стены ($l_i < r_i$). Известно, что на каждый колышек натянута ровно одна ниточка.

С ниточками можно производить операции \textit{перенатягивания}. За одну операцию \textit{перенатягивания} можно выбрать две ниточки $(l_i, r_i)$ и $(l_j, r_j)$, снять их с колышков, а затем повесить две новые ниточки, использовав каждый из четырёх освободившихся колышков ровно один раз. То есть из четырёх освободившихся колышков составляются две новые пары, между которыми натягиваются новые ниточки.

Ниточки, натянутые между колышками $(l_i, r_i)$ и $(l_j, r_j)$, пересекаются, если отрезки $[l_i, r_i]$ и $[l_j, r_j]$ имеют хотя бы одну общую точку. Считается, что конфигурация из ниточек имеет красоту хотя-бы $k$, если существует множество из $k$ ниточек, каждая пара из которых пересекается. Обратите внимание, что если конфигурация имеет красоту $k$, то она в том числе имеет красоту хотя-бы $k - 1,\ k - 2,\ \ldots,\ 0$.

У организаторов олимпиады есть $q$ запросов получения конфигурации некоторой красоты в результате применения нескольких операций \textit{перенатягивания}. В $i$-м запросе они бы хотели получить красоту хотя-бы $k_i$. Для каждого из запросов организаторам хочется узнать, какое минимальное количество операций \textit{перенатягивания} необходимо совершить, чтобы этого добиться. Запросы независимы между собой. То есть операции \textit{перенатягивания} между запросами не сохраняются.