1221 — Eolymp

Input

The first line contains a single integer $t$ $(1 \leq t \leq 100)$ (1 \le t \le 100) — the number of test cases.

For each test case: The first line contains a single integer $n$ $(2 \leq n \leq 2000)$ (2 \le n \le 2000) — the length of arrays $a$ and $b$ .

The second line contains $n$ integers $a_{1}, a_{2}, \dots, a_{n}$ a_1,a_2,\dots,a_n $(1 \leq a_{i} \leq 1 0^{9})$ (1 \le a_i \le 10^9) — the elements of array $a$ .

The third line contains $n$ integers $b_{1}, b_{2}, \dots, b_{n}$ b_1,b_2,\dots,b_n $(1 \leq b_{i} \leq 1 0^{9})$ (1 \le b_i \le 10^9) — the elements of array $b$ .

It is guaranteed that the sum of $n$ over all test cases does not exceed $2000$ .

Output

For each test case, output a single integer — the total number of valid triplets.

Examples

Example 1

Loading

Note

In the first test case , the only way to form a valid triplet

Pick $x = a_{1} = 2$ x=a_1=2 , $y = a_{2} = 3$ y=a_2=3 from array $a$ and $z = b_{1} = 4$ z=b_1=4 from array $b$

In the second test case , there are three ways to form a valid triplet

$(2, 3, 2)$ (2,3,2) Pick $x = a_{1} = 2$ x=a_1=2 , $y = a_{2} = 3$ y=a_2=3 from array $a$ and $z = b_{1} = 2$ z=b_1=2 from array $b$
$(2, 3, 4)$ (2,3,4) Pick $x = a_{1} = 2$ x=a_1=2 , $y = a_{2} = 3$ y=a_2=3 from array $a$ and $z = b_{2} = 4$ z=b_2=4 from array $b$
$(2, 4, 3)$ (2,4,3) Pick $x = b_{1} = 2$ x=b_1=2 , $y = b_{2} = 4$ y=b_2=4 from array $b$ and $z = a_{2} = 3$ z=a_2=3 from array $a$

In the third test case , there are six ways to form a valid triplet

Pick $x = a_{1} = 1$ x=a_1=1 , $y = a_{2} = 1$ y=a_2=1 from array $a$ and $z = b_{1} = 1$ z=b_1=1 from array $b$
Pick $x = a_{1} = 1$ x=a_1=1 , $y = a_{3} = 1$ y=a_3=1 from array $a$ and $z = b_{1} = 1$ z=b_1=1 from array $b$
Pick $x = a_{2} = 1$ x=a_2=1 , $y = a_{3} = 1$ y=a_3=1 from array $a$ and $z = b_{1} = 1$ z=b_1=1 from array $b$
Pick $x = b_{2} = 2$ x=b_2=2 , $y = b_{3} = 2$ y=b_3=2 from array $b$ and $z = a_{1} = 1$ z=a_1=1 from array $a$
Pick $x = b_{2} = 2$ x=b_2=2 , $y = b_{3} = 2$ y=b_3=2 from array $b$ and $z = a_{2} = 1$ z=a_2=1 from array $a$
Pick $x = b_{2} = 2$ x=b_2=2 , $y = b_{3} = 2$ y=b_3=2 from array $b$ and $z = a_{3} = 1$ z=a_3=1 from array $a$

Scoring

Subtask $1$ ( $40$ points) : $(1 \leq \sum n \leq 100)$ (1 \le \sum n \le 100)
Subtask $2$ ( $60$ points) : $(1 \leq a_{1}, a_{2}, \dots, a_{n} \leq 10)$ (1 \le a_1,a_2,\ldots,a_n \le 10) and $(1 \leq b_{1}, b_{2}, \dots, b_{n} \leq 10)$ (1 \le b_1,b_2,\ldots,b_n \le 10).
Subtask $3$ ( $100$ points) : No additional constraints