Efficient Computation of a Recursive Boolean Function

Byteasar is tasked with computing the Boolean function \(F(x,y)\) for two positive integer sequences \(x=(x_1,x_2,\dots,x_n)\) and \(y=(y_1,y_2,\dots,y_n)\). The function is defined as follows:

1. If \(W(x)\neq W(y)\) then \(F(x,y)=0\),
2. If \(|W(x)| = |W(y)| = 1\) then \(F(x,y)=1\),
3. Otherwise, \(F(x,y)=F(p(x),p(y)) \wedge F(s(x),s(y))\).

Here:

• \(W(x)\) denotes the set of distinct members from \(x\) (order and repetitions are insignificant),
• \(p(x)\) denotes the longest prefix of \(x\) such that \(W(p(x))\) is a proper subset of \(W(x)\). In other words, if we scan \(x\) from the beginning and stop right before the prefix becomes equal to the full set \(W(x)\), that prefix is \(p(x)\). For example, for \(x=(2,3,7,2,7,4,7,2,4)\) with \(W(x)=\{2,3,4,7\}\), we have \(p(x)=(2,3,7,2,7)\) because the next element would complete the set.
• \(s(x)\) denotes the longest suffix of \(x\) such that \(W(s(x))\) is a proper subset of \(W(x)\). This is derived similarly by scanning from the end. In the example, \(s(x)=(7,2,7,4,7,2,4)\) because omitting the unique element (here, \(3\)) ensures it remains a proper subset.
• \(\wedge\) denotes logical conjunction (AND), where \(1\) represents true and \(0\) represents false.

Your task is to compute \(F(x,y)\) for multiple test cases as fast as possible.

inputFormat

The first line of input contains an integer \(T\), the number of test cases. Each test case consists of three lines:

• The first line contains an integer \(n\) \((1 \le n)\) representing the length of the sequences.
• The second line contains \(n\) positive integers representing the sequence \(x\).
• The third line contains \(n\) positive integers representing the sequence \(y\).

outputFormat

For each test case, output a single line containing \(0\) or \(1\), the value of \(F(x,y)\).

sample

1
5
7 7 7 7 7
7 7 7 7 7

1