Problem Description

A school has a total of $3*n$ students, divided evenly into $A$ group, $B$ group or $C$ group, with $n$ in each group. Everyone has an ability value $v_i$, the tacit value between two students is $f(i,j)=(v_i+v_j)*(v_i \oplus v_j) \% M$, where $\oplus$ means bitwise exclusive OR operation. As the competition coach of this school, you need to select exactly $m$ teams to participate in the $CCPC$ competition in the second half of the year.

Specifically, Each team contains exactly three students, and the three students are from different groups.
Let the team members from the $A,B,C$ group be $a,b,c$, then the tacit value of this team is $f(a,b)+f(a,c)$.

Please find out the maximum sum of the tacit values of the $m$ teams.

Input

The input consists of multiple test cases. The first line contains an integer $T$ $(1 \leq T \leq 10)$ — the number of test cases.
The description of the test cases follows.

The first line contains three integers $n,m,M$ $(1 \leq m \leq n \leq 200,10 \leq M \leq 2000)$.

Then follows three lines, each line contains $n$ integers $v_1,v_2,\dots,v_n$ $(1 \leq v_i \leq 2000)$ — the ability value of each student in group $A,B$ and $C$ .

Output

For each test case, print the answer.

2
3 2 10
1 2 3
4 5 6
7 8 9
4 4 21
5 4 2 6
9 1 10 2
4 3 99 12

27
98