{"raw_statement":[{"iden":"problem statement","content":"> The problem setting of this problem is partially shared with Problem F.\n\nIn the year $2222$, CatCoder will hold the CatCoder Double Contest (abbreviated as C2C).\nThere are $N$ writers who have problem proposals. Each writer's problem proposals are classified into $3$ types by difficulty: Hard, Medium, Easy, and the $i$\\-th writer has $A_i$, $B_i$, $C_i$ problem proposals of Hard, Medium, Easy, respectively.\nEach C2C simultaneously holds $2$ divisions, Div.1 and Div.2. The problem proposals required for each division are as follows:\n\n*   Div.1: One Hard and one Medium problem proposal from the same writer\n*   Div.2: One Medium and one Easy problem proposal from the same writer\n\nNote that **the writers for Div.1 and Div.2 do not necessarily have to be the same**. Also, each problem proposal can be used in at most one division of one C2C.\nFind the maximum number of times C2C can be held.\n$T$ test cases are given, so find the answer for each."},{"iden":"constraints","content":"*   $1 \\le T \\le 10^5$\n*   $1 \\le N \\le 2 \\times 10^5$\n*   $1 \\le A_i,B_i,C_i \\le 10^9$\n*   The sum of $N$ over all test cases is at most $2 \\times 10^5$.\n*   All input values are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$T$\n$\\text{case}_1$\n$\\text{case}_2$\n$\\vdots$\n$\\text{case}_T$\n\nEach test case is given in the following format:\n\n$N$\n$A_1$ $B_1$ $C_1$\n$A_2$ $B_2$ $C_2$\n$\\vdots$\n$A_N$ $B_N$ $C_N$"},{"iden":"sample input 1","content":"5\n2\n3 1 4\n1 5 3\n1\n1 1 1\n3\n5 7 5\n1 11 99\n3 1 2\n5\n1000000000 1000000000 1000000000\n1000000000 1000000000 1000000000\n1000000000 1000000000 1000000000\n1000000000 1000000000 1000000000\n1000000000 1000000000 1000000000\n6\n835549144 866512240 105679868\n473233032 625162103 823002638\n125467290 37501686 380787083\n8043910 721085797 254272563\n97327826 744196952 18713225\n978152989 90127986 33086297"},{"iden":"sample output 1","content":"2\n0\n7\n2500000000\n998830769\n\nFor the first test case, C2C can be held $2$ times by using problem proposals as follows:\n\nDiv.1\n\nDiv.2\n\n$1$st time\n\nHard, Medium from the $1$st writer\n\nMedium, Easy from the $2$nd writer\n\n$2$nd time\n\nHard, Medium from the $2$nd writer\n\nMedium, Easy from the $2$nd writer"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}