Jaccard Similarity Threshold

Interview

Time limit1sMemory limit512 MB

Summary

Given two small sets of digits, decide whether their Jaccard similarity is greater than 0.5.

Level: Easy2 of 10
Topics: Implementation, Math
Solved: No attempts yet

Problem

The Jaccard similarity coefficient measures how similar two sets are. For two sets $A$ and $B$ , the coefficient $J(A, B)$ is the size of the intersection divided by the size of the union, that is $J(A, B) = \frac{|A \cap B|}{|A \cup B|}$ . For example, if $A = \{1, 3, 7, 8\}$ and $B = \{1, 7, 9\}$ , then $J(A, B) = \frac{|\{1, 7\}|}{|\{1, 3, 7, 8, 9\}|} = \frac{2}{5}$ .

Every element of a set is an integer between 0 and 9, and no set holds more than 10 elements. Given two sets $A$ and $B$ , compute $J(A, B)$ and print 1 when $J(A, B) > 0.5$ , or 0 when $J(A, B) \le 0.5$ .

Input

The first line contains the number of test cases $T$ ( $1 \le T \le 25$ ).

Each test case consists of three lines. The first line contains $m$ and $n$ , the number of elements of $A$ and the number of elements of $B$ ( $1 \le m, n \le 10$ ). The second line contains the $m$ elements of $A$ and the third line contains the $n$ elements of $B$ , separated by spaces. Every element is an integer between 0 and 9, and the same value never appears twice inside one set.

Output

For each test case, print 1 if $J(A, B) > 0.5$ and 0 if $J(A, B) \le 0.5$ , one answer per line.

Examples4

Example 1

Input

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

Expected output

0
1
1

Example 2
Input
```
1
1 1
5
5
```
Expected output
```
1
```
Example 3
Input
```
1
1 1
0
9
```
Expected output
```
0
```
Example 4
Input
```
2
3 3
1 2 3
1 2 4
2 4
1 2
1 2 3 4
```
Expected output
```
0
0
```