B'The easy and hard versions of this problem differ only in the constraints on the number of test cases and n . In the hard version, the number of test cases does not exceed 10^4 , and the sum of values of n over all test cases does not exceed 2 cdot 10^5 . Furthermore, there are no additional constraints on n in a single test case. Recently, Alice and Bob were given marbles of n different colors by their parents. Alice has received a_1 marbles of color 1 , a_2 marbles of color 2 ,..., a_n marbles of color n . Bob has received b_1 marbles of color 1 , b_2 marbles of color 2 , ..., b_n marbles of color n . All a_i and b_i are between 1 and 10^9 . After some discussion, Alice and Bob came up with the following game: players take turns, starting with Alice. On their turn, a player chooses a color i such that both players have at least one marble of that color. The player then discards one marble of color i , and their opponent discards all marbles of color i . The game ends when there is no color i such that both players have at least one marble of that color. The score in the game is the difference between the number of remaining marbles that Alice has and the number of remaining marbles that Bob has at the end of the game. In other words, the score in the game is equal to (A-B) , where A is the number of marbles Alice has and B is the number of marbles Bob has at the end of the game. Alice wants to maximize the score, while Bob wants to minimize it. Calculate the score at the end of the game if both players play optimally. The first line contains a single integer t ( 1 <= t <= 10^4 ) -- the number of test cases. Each test case consists of three lines: Additional constraint on the input: the sum of n for all test cases does not exceed 2 cdot 10^5 . For each test case, output a'...