During the preparation for the Closed Olympiad of School Students in Programming, the organizers decided to decorate the auditorium. For this purpose, $2n$ pegs were hammered into a straight line on the wall. All pegs are in different positions. Between them, $n$ strings were stretched, the $i$-th of which was stretched between the pegs at distances $l_i$ and $r_i$ from the start of the wall ($l_i < r_i$). It is known that each peg has exactly one string stretched to it.

The strings can undergo operations called \textit{restringing}. In one \textit{restringing} operation, you can choose two strings $(l_i, r_i)$ and $(l_j, r_j)$, remove them from the pegs, and then hang two new strings, using each of the four freed pegs exactly once. That is, from the four freed pegs, two new pairs are formed, between which new strings are stretched.

The strings stretched between the pegs $(l_i, r_i)$ and $(l_j, r_j)$ intersect if the segments $[l_i, r_i]$ and $[l_j, r_j]$ have at least one common point. A configuration of strings is considered to have beauty at least $k$ if there exists a set of $k$ strings, each pair of which intersects. Note that if a configuration has beauty $k$, it also has beauty at least $k - 1,\ k - 2,\ \ldots,\ 0$.

The organizers of the Olympiad have $q$ queries for obtaining a configuration of a certain beauty as a result of several \textit{restringing} operations. In the $i$-th query, they would like to achieve beauty at least $k_i$. For each query, the organizers want to know the minimum number of \textit{restringing} operations required to achieve this. The queries are independent of each other, meaning that the \textit{restringing} operations between queries are not preserved.