В процеса на подготовка организаторите на Закритата ученическа олимпиада по програмиране решили да украсят аудиторията. За целта, на стената в една права са забити $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{пренатягане} не се съхраняват между заявките.