CF2273D Aura Battle

This is an interactive problem. Hacks are disabled. You're in an aura battle in Pachuca, Mexico. Each battle consists of $ 10 $ rounds. The judges have a hidden integer $ x $ ( $ 1 \le x \le 10^4 $ ), which remains fixed throughout the battle. In round $ i $ , you choose two integers $ a_i $ and $ b_i $ ( $ -10^9 \le a_i, b_i \le 10^9 $ ). You then lose $$$ \min\bigl(|x-a_i|,\ |x-b_i|\bigr) $$$ aura and are told this amount before the next round begins. Your choices may depend on the results of all previous rounds. After the battle is over, your total aura loss is calculated as the sum of the aura lost in each of the $ 10 $ rounds. Let $ m $ be the smallest integer such that there exists a strategy guaranteeing a total aura loss of at most $ m $ , regardless of the hidden value of $ x $ . Your task is to guarantee a total aura loss not exceeding the limit, which is $ 10^5 $ on the first test (the example) and $ m+67 $ on all other tests.

The first line of input contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of battles.

N/A

In the example there is a single battle, and the hidden value $ x $ is $ 40 $ . - In the first round, $ a_1 = 3 $ and $ b_1 = 53 $ , so you lose $ 13 = \min(\lvert 3 - 40 \rvert, \lvert 53 - 40 \rvert) $ aura. - In the second round, $ a_2 = 36 $ and $ b_2 = 49 $ , so you lose $ 4 = \min(\lvert 36 - 40 \rvert, \lvert 49 - 40 \rvert) $ aura. - In the third round, the amount of aura you lose is $ 2 $ . - In the following rounds, the amount of aura you lose is $ 2, 4, 5, 9, 6, 9, 13 $ respectively. The total amount of aura you lose is $ 67 $ . Note that this is an example of how the interaction works. To receive an accepted verdict, you must solve the problem without exceeding the aura limit outlined in the statement above.