Surely you have heard of Japanese ninjas. What you probably didn't know is that there are also Spanish ninjas, but you have never heard of them because they are much better than the Japanese. In fact, throughout the history of Spain, they have only been caught once, trying to infiltrate the royal palace. Here are the chronicles.

The royal palace consists of $$$n$$$ rooms numbered from $$$0$$$ to $$$n - 1$$$, connected to each other by $$$n - 1$$$ corridors, all of equal length, so that from any room you can reach any other without leaving the palace. It also has multiple entrances: in each room that has only one corridor, there is a door that allows entry and exit from the palace through it.

A very large group of ninjas is ready to enter the palace to set an ambush for the king. Just as they are about to enter, an even larger group of royal guards spots them. At this moment, the ninjas quickly choose a door and all enter through it, and the guards, who have seen where the ninjas enter but do not have time to run towards them, choose another door and all enter through it.

Once inside, since both the ninjas and the guards move at the same speed, each room is occupied by the group that started closest to it, and in case of a tie, the guards take it (see the examples). The ninjas' goal is to occupy the maximum number of rooms possible, and the guards' goal is to ensure that the ninjas occupy the minimum possible. Knowing that both choose their starting room optimally, how many rooms do the ninjas occupy in the end?

For all test cases, it holds that $$$t \leq 100$$$, $$$2 \leq n$$$, $$$0 \leq a_i, b_i \lt n$$$

5 points: $$$n \leq 5$$$

16 points: $$$n \leq 70$$$

22 points: $$$n \leq 500$$$

57 points: $$$n \leq 10000$$$