F. Подсчет необходимых узлов
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Квадродерево — это древовидная структура данных, в которой каждый узел имеет не более четырех дочерних узлов и отвечает за квадратную область.

Формально, для всех кортежей неотрицательных целых чисел $$$k,a,b \ge 0$$$ существует ровно один узел, отвечающий за следующую область$$$^{\text{∗}}$$$.

$$$$$$[a \cdot 2^k,(a+1) \cdot 2^k] \times [b \cdot 2^k,(b+1) \cdot 2^k]$$$$$$

Все узлы, чья область больше $$$1 \times 1$$$, содержат четыре дочерних узла, соответствующих областям, разделенным поровну на четыре, а узлы, чья область равна $$$1 \times 1$$$, соответствуют листам дерева.

Показано небольшое подмножество областей, за которые отвечают узлы. Относительно более темные области ближе к листам.

Фронтмен ненавидит широко распространенное заблуждение, что квадродерево может выполнять запросы диапазона за $$$\mathcal{O}(\log n)$$$ времени, когда в области находится $$$n$$$ листовых узлов. На самом деле, иногда необходимо запрашивать гораздо больше, чем $$$\mathcal{O}(\log n)$$$ областей для этого, и временная сложность в некоторых крайних случаях составляет $$$\mathcal{O}(n)$$$. Таким образом, Фронтмен придумал эту задачу, чтобы просветить вас о худшем случае этой структуры данных.

Розовые солдаты дали вам конечную область $$$[l_1,r_1] \times [l_2,r_2]$$$, где $$$l_i$$$ и $$$r_i$$$ ($$$l_i \lt r_i$$$) — неотрицательные целые числа. Найдите минимальное количество узлов, которые вы должны выбрать, чтобы объединение областей, за которые отвечают выбранные узлы, ровно совпадало с данной областью. Здесь два множества точек считаются различными, если существует точка, включенная в одно, но не в другое.

$$$^{\text{∗}}$$$Области — это множества точек с действительными координатами, где точка $$$(x,y)$$$ включена в область $$$[p,q] \times [r,s]$$$ тогда и только тогда, когда $$$p \le x \le q$$$ и $$$r \le y \le s$$$. Здесь $$$\times$$$ формально относится к декартову произведению множеств.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Единственная строка каждого набора содержит четыре целых числа $$$l_1$$$, $$$r_1$$$, $$$l_2$$$, $$$r_2$$$ — границы области по каждой оси ($$$0 \le l_i \lt r_i \le 10^6$$$).

Выходные данные

Для каждого набора входных данных выведите минимальное количество узлов, необходимых для удовлетворения условия, на отдельной строке.

Пример
Входные данные
5
0 1 1 2
0 2 0 2
1 3 1 3
0 2 1 5
9 98 244 353
Выходные данные
1
1
4
5
374
Примечание

В первом примере данная область — $$$[0,1] \times [1,2]$$$. Существует один узел, отвечающий за $$$[0,1] \times [1,2]$$$. Выбирая этот узел, ответ равен $$$1$$$.

Во втором примере данная область — $$$[0,2] \times [0,2]$$$. Существует один узел, отвечающий за $$$[0,2] \times [0,2]$$$. Выбирая этот узел, ответ равен $$$1$$$.

В третьем примере данная область — $$$[1,3] \times [1,3]$$$. Существует нет узла, который отвечает за $$$[1,3] \times [1,3]$$$. Вместо этого вы можете сделать объединение областей ровно таким же, как $$$[1,3] \times [1,3]$$$, выбрав следующие $$$4$$$ узла:

  • Листовой узел, отвечающий за $$$[1,2] \times [1,2]$$$;
  • Листовой узел, отвечающий за $$$[1,2] \times [2,3]$$$;
  • Листовой узел, отвечающий за $$$[2,3] \times [1,2]$$$;
  • Листовой узел, отвечающий за $$$[2,3] \times [2,3]$$$.

Можно показать, что невозможно сделать объединение областей ровно таким же, как $$$[1,3] \times [1,3]$$$, с менее чем $$$4$$$ узлами. Поэтому ответ равен $$$4$$$.

В четвертом примере данная область — $$$[0,2] \times [1,5]$$$. Вы можете сделать объединение областей ровно таким же, как $$$[0,2] \times [1,5]$$$, выбрав следующие $$$5$$$ узлов:

  • Листовой узел, отвечающий за $$$[0,1] \times [1,2]$$$;
  • Листовой узел, отвечающий за $$$[1,2] \times [1,2]$$$;
  • Нелистовой узел, отвечающий за $$$[0,2] \times [2,4]$$$;
  • Листовой узел, отвечающий за $$$[0,1] \times [4,5]$$$;
  • Листовой узел, отвечающий за $$$[1,2] \times [4,5]$$$.

Можно показать, что невозможно сделать объединение областей ровно таким же, как $$$[0,2] \times [1,5]$$$, с менее чем $$$5$$$ узлами. Поэтому ответ равен $$$5$$$.