Years later, Shiro and White both enrolled in THU. After learning about the EXP3 algorithm for the "Multi-armed Bandit" problem in class, they suddenly had a whim and devised a game unrelated to this. There are (n) positions arranged in a row, numbered (1,2,\ldots,n) from front to back. Each position can be in one of two states: blackened or unblackened . Shiro's piece starts at position (1), and White's piece starts at position (2). At the beginning of the game, only positions (1) and (2) are blackened . The players take turns making moves, with Shiro going first. In each turn, the current player must choose their own piece and jump forward (1) to (4) steps to an unblackened position, and blacken the position they land on. If a player cannot make a legal move (i.e., all positions within (1) to (4) steps forward from their current position are either beyond (n) or already blackened ), the player will skip this turn (i.e., make no move). The game ends when both Shiro and White cannot make any valid move. It is easy to prove that the game is guaranteed to terminate within a finite number of steps. For each (3\le k\le n), position (k) has a positive integer weight (a_k). Whenever a player blackens such a position (k), their score increases by (a_k). Both Shiro and White start with a score of (0), and both of them aim to maximize the difference between their own score and their opponent's score by the end of the game. Let (d=s_1 - s_2), where (s_1) is Shiro's score and (s_2) is White's score. Shiro and White want to know: if both players act according to optimal strategies, what will be the value of (d) after the game ends? Since this problem is too complex, they have turned to you from THUSAA. You have to help them solve the problem. Each test contains multiple test cases. The first line contains the number of test cases (t) ((1 \le t \le 1000)). The description of the