Стена

По дороге в школу Петя Пяточкин проходит мимо стены, на которую жители его города любят клеить рекламные объявления. Каждое объявление — это прямоугольный кусок бумаги с целыми длинами сторон, и его приклеивают к стене ровно. Часть одного объявления или даже всё оно может быть покрыто другим объявлением или несколькими объявлениями. Первого числа каждого месяца все рекламные объявления со стены убирают, но уже второго числа утром содержимое стены чудесным образом восстанавливается. Петя заметил, что рекламные объявления на стене каждый месяц те же самые — n прямоугольников, окрашенных в n разных цветов, и расположено каждое объявление всегда на одном и том же месте стены. Петя предположил, однако, что объявления клеят на стену в разном порядке.

Помогите Пете выяснить, сможет ли он всегда, посмотрев на стену, однозначно восстановить порядок, в котором на неё наклеили объявления.

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

В первой строке входного файла указано натуральное число t ≤ 5 — количество тестов в файле. Далее следует t блоков, соответствующих t различным тестам. Блоки не разделены пустыми строками.

В первой строке каждого блока указано натуральное число n ≤ 10000 — количество рекламных объявлений на стене.

В (i+1)-й строке блока (1 ≤ i ≤ n) указаны параметры i-го объявления: натуральные числа x_i, y_i, w_i, h_i, не превышающие 10000, — соответственно расстояние от левой стороны объявления до левого края стены, расстояние от верхней стороны объявления до верхней границы стены, ширина и высота i-го объявления.

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

Выходной файл должен содержать t чисел, каждое в своей строке: i-е число должно быть единицей, если для i-го теста Петя всегда сможет восстановить последовательность наклеивания объявлений, или нулём, если он не всегда сможет это сделать.

Примеры

Примечание

По условиям первого теста на стену клеят два объявления, которые частично перекрываются (см. рис. 1). Петя всегда сможет определить, какое из них наклеили первым, а какое — вторым.

Рис. 1. При таком расположении объявлений на стене Петя всегда сможет определить порядок наклеивания: слева белое объявление наклеили первым, серое вторым, а справа — наоборот.

Во втором тесте два объявления висят на стене рядом. Петя никогда не сможет точно определить, в каком порядке их наклеили.

В третьем тесте к двум объявлениям из второго теста добавляется ещё одно. Хотя объявления могут быть наклеены в таком порядке, что Петя однозначно сможет его восстановить (например, в порядке, в котором они указаны во входном файле), но их могут наклеить и так, что порядок однозначно восстановить невозможно (например, сначала "среднее" объявление, а потом два других).