Problem Description

A sequence $S$ of length $5$ is defined as “good” if and only if there exists a permutation $P$ of length $5$ such that $S_{P_1}-1=S_{P_2}=S_{P_3}+1$ and $S_{P_4}=S_{P_5}$. Now you are given an integer sequence $a$ of length $5$, satisfying $0\le a_i \le 9(1\le i \le 5)$. Among them, $a_1 \sim a_4$ are given. Determine whether there exists an $a_5$ such that $a$ is “good”.

Here, a permutation $P$ of length $5$ means a sequence of length $5$ in which $1,2,3,4,5$ each appears exactly once.

Input Format

This problem contains multiple test cases.

• The first line contains an integer $T$, the number of test cases.
• The next $T$ lines each contain four integers $a_1,a_2,a_3,a_4$, representing one test case.

Output Format

• Output $T$ lines in total. For each test case, if there exists an $a_5$ that satisfies the condition, output $1$; otherwise output $0$.

5
3 2 8 4
1 2 3 4
1 9 4 9
1 0 0 1
0 0 4 2

1
1
0
0
1

Hint

Additional Samples

• Sample $2$ can be found in the distributed file $\textbf{\textit{one2.in/one2.ans}}$. This sample satisfies the constraints of test point $2$.
• Sample $3$ can be found in the distributed file $\textbf{\textit{one3.in/one3.ans}}$. This sample satisfies the constraints of test point $5$.

Sample Explanation

Sample #1

• For the $1$st test case, we can set $a_5=8$. Then there exists $P=\{4,1,2,5,3\}$ such that $a_{P_1}-1=a_{P_2}=a_{P_3}+1$ and $a_{P_4}=a_{P_5}$. Therefore output $1$.
• For the $2$nd test case, we can set $a_5=4$. Then there exists $P=\{3,2,1,4,5\}$ such that $a_{P_1}-1=a_{P_2}=a_{P_3}+1$ and $a_{P_4}=a_{P_5}$. Therefore output $1$.
• For the $3$rd test case, there is no $a_5$ that can make $a$ “good”.

$$\begin{aligned} \fcolorbox{black}{#fbb}{3\ \ 2\ \ 8\ \ 4} + \fcolorbox{black}{yellow}{8} &\Rightarrow \fcolorbox{black}{#fbb}{2\ \ 3\ \ 4} + \fcolorbox{black}{yellow}{8\ \ 8}\ {\color{green}\sqrt{}}\\ \fcolorbox{black}{#fbb}{1\ \ 2\ \ 3\ \ 4} + \fcolorbox{black}{yellow}{4} &\Rightarrow \fcolorbox{black}{#fbb}{1\ \ 2\ \ 3} + \fcolorbox{black}{yellow}{4\ \ 4}\ {\color{green}\sqrt{}}\\ \fcolorbox{black}{#fbb}{1\ \ 9\ \ 4\ \ 9} + \begin{cases} \fcolorbox{black}{yellow}{0}\\ \fcolorbox{black}{yellow}{1}\\ \cdots\\ \fcolorbox{black}{yellow}{9} \end{cases}&\Rightarrow {\color{red}\xcancel{\color{black} \begin{cases} \fcolorbox{black}{#fbb}{1\ \ 9\ \ 4\ \ 9\ \ 0}\\ \fcolorbox{black}{#fbb}{1\ \ 9\ \ 4\ \ 9\ \ 1}\\ \cdots\\ \fcolorbox{black}{#fbb}{1\ \ 9\ \ 4\ \ 9\ \ 9} \end{cases}}} \end{aligned}$$

Constraints

$$\def\arraystretch{1.5} \begin{array}{|c|c|c|} \hline \textbf{\textsf{Test Point}} & \bm{{T\le}} & \textbf{\textsf{Special Property}} \cr\hline 1 & 100 & \textbf{A} \cr\hline 2 & 100 & \textbf{B} \cr\hline 3 & 100 & - \cr\hline 4 & 1000 & - \cr\hline 5 & 10^5 & - \cr\hline \end{array}$$

• Special property $\bf A$: $a_1=a_2=a_3=a_4$.
• Special property $\bf B$: $a_1,a_2,a_3,a_4$ are pairwise distinct.

For $100\%$ of the testdata, $1\le T\le 10^5$, $0\le a_i \le 9$.

Translated by ChatGPT 5