{"raw_statement":[{"iden":"problem statement","content":"You are given two sequences of positive integers of length $N$, $A=(A_1,A_2,\\dots,A_N)$ and $B=(B_1,B_2,\\dots,B_N)$.\nFind the minimum possible inversion number of a sequence of positive integers $C=(C_1,C_2,\\dots,C_N)$ such that the $i$\\-th element $C_i$ is $A_i$ or $B_i$.\nSolve $T$ test cases."},{"iden":"constraints","content":"*   $1 \\le T$\n*   $1 \\le N \\le 5 \\times 10^5$\n*   $1 \\le A_i,B_i \\le \\color{red}{\\boldsymbol{3}}$\n*   The sum of $N$ for all test cases in a single input is at most $5 \\times 10^5$."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$T$\n$\\mathrm{case}_1$\n$\\mathrm{case}_2$\n$\\vdots$\n$\\mathrm{case}_T$\n\nHere, $\\mathrm{case}_i$ represents the $i$\\-th test case. Each test case is given in the following format:\n\n$N$\n$A_1$ $A_2$ $\\dots$ $A_N$\n$B_1$ $B_2$ $\\dots$ $B_N$"},{"iden":"sample input 1","content":"8\n3\n2 1 1\n3 3 2\n5\n2 1 3 2 2\n1 2 1 2 3\n8\n2 1 3 3 3 1 2 2\n1 2 3 1 2 1 3 2\n10\n1 3 2 1 1 3 2 2 2 2\n2 3 1 1 1 1 3 1 3 3\n12\n2 1 1 3 3 1 3 3 2 2 2 1\n3 1 1 3 3 1 3 2 3 2 1 2\n15\n1 3 1 3 3 2 2 1 2 3 3 3 1 1 3\n3 3 3 2 3 2 1 3 2 1 2 2 3 3 3\n18\n3 1 1 3 3 2 1 1 2 3 2 1 3 3 3 2 2 3\n1 1 3 2 1 3 1 2 1 2 3 2 2 1 3 1 3 3\n20\n2 2 3 1 1 3 2 3 3 1 3 1 2 1 2 2 1 2 3 2\n1 1 1 3 3 1 1 3 2 2 1 1 1 1 1 2 2 2 2 1"},{"iden":"sample output 1","content":"1\n0\n6\n6\n20\n9\n5\n17\n\nFor the first test case, an optimal solution is $C=(2,3,2)$ with the inversion number of $1$.\nFor the second test case, an optimal solution is $C=(1,1,1,2,3)$ with the inversion number of $0$."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}