If it was so, then let's make it a deal...— MayDay, Gentleness

Even after copying the paintings from famous artists for ten years, unfortunately, Eric is still unable to become a skillful impressionist painter. He wants to forget something, but the white bear phenomenon just keeps hanging over him.

Eric still remembers $n$ pieces of impressions in the form of an integer array. He records them as $w_1, w_2, \ldots, w_n$. However, he has a poor memory of the impressions. For each $1 \leq i \leq n$, he can only remember that $l_i \leq w_i \leq r_i$.

Eric believes that impression $i$ is unique if and only if there exists a possible array $w_1, w_2, \ldots, w_n$ such that $w_i \neq w_j$ holds for all $1 \leq j \leq n$ with $j \neq i$.

Please help Eric determine whether impression $i$ is unique for every $1 \leq i \leq n$, independently for each $i$. Perhaps your judgment can help rewrite the final story.

Input

Each test contains multiple test cases. The first line of the input contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer $n$ ($1 \leq n \leq 2\cdot 10^5$) — the number of impressions.

Then $n$ lines follow, the $i$-th containing two integers $l_i$ and $r_i$ ($1 \leq l_i \leq r_i \leq 2\cdot n$) — the minimum possible value and the maximum possible value of $w_i$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$.

Output

For each test case, output a binary string $s$ of length $n$: for each $1 \leq i \leq n$, if impression $i$ is unique, $s_i=\texttt{1}$; otherwise, $s_i=\texttt{0}$. Do not output spaces.

Note

In the first test case, the only possible array $w$ is $[1, 1]$, making neither impression $1$ nor $2$ unique (since $w_1 = w_2$).

In the second test case, all impressions can be made unique:

• For $i = 1$, we can set $w$ to $[1, 3, 2, 3]$, in which $w_1 \neq w_2$, $w_1 \neq w_3$, and $w_1 \neq w_4$;
• For $i = 2$, we can set $w$ to $[2, 3, 1, 2]$, in which $w_2 \neq w_1$, $w_2 \neq w_3$, and $w_2 \neq w_4$;
• For $i = 3$, we can set $w$ to $[1, 1, 3, 1]$;
• For $i = 4$, we can set $w$ to $[2, 3, 3, 1]$.

In the third test case, for $i = 4$, we can set $w$ to $[3, 2, 2, 1, 3, 2]$. Thus, impression $4$ is unique.