Wall
On his way to school, Petro Pyatochkin passes by a wall where the residents of his city like to post advertisements. Each advertisement is a rectangular piece of paper with integer side lengths, neatly placed on the wall. Some advertisements may partially or completely cover others. On the first day of each month, all advertisements are removed, but by the morning of the second day, they magically reappear in the same arrangement. Petryk has observed that the advertisements are always the same each month — n rectangles, each in a different color, and always positioned in the same spots. However, he suspects that the order in which they are posted might change.
Your task is to help Petryk determine if he can always uniquely deduce the order in which the advertisements were posted by observing the wall.
Input
The first line of the input contains a natural number t ≤ 5 — the number of test cases. Each test case is described in a block, with no empty lines between them.
The first line of each block contains a natural number n ≤ 10000 — the number of advertisements on the wall.
For each advertisement, the (i+1)-th line of the block (1 ≤ i ≤ n) provides the parameters: natural numbers x_i, y_i, w_i, h_i, each not exceeding 10000. These represent the distance from the left edge of the advertisement to the left edge of the wall, the distance from the top edge of the advertisement to the top edge of the wall, the width, and the height of the i-th advertisement, respectively.
Output
The output should contain t numbers, each on a new line: the i-th number should be one if Petryk can always determine the order in which the advertisements were posted for the i-th test, or zero if he cannot.
Explanation of the example
In the first test case, two advertisements overlap partially (see Fig. 1). Petryk can always tell which was posted first and which second.
Fig. 1. In this arrangement, Petryk can always determine the posting order: on the left, the white advertisement was posted first, followed by the gray one; on the right, the order is reversed.
In the second test case, two advertisements are side by side. Petryk cannot determine the posting order.
In the third test case, an additional advertisement is added to the two from the second test. Although the advertisements can be posted in an order that allows Petryk to determine it uniquely (e.g., in the order given in the input), they can also be posted in a way that makes the order indeterminable (e.g., posting the "middle" one first, followed by the others).