409672: GYM103677 I Faction Feud

For generations, the Grape and Raisin factions were the greatest of allies. Each night at dinnertime, both factions would sit down and enjoy a meal together at their shared circular table. The factions had a very particular seating manner in order to ensure peaceful relations. As both factions have an equal number of members, no two members of the same faction may sit next to each other. This seating method ensures the maximum number of healthy conversations between members of different factions.

One day, a nasty feud broke out between the factions. It began with a brawl, during which the members of both factions were scrambled about. This means that the rule governing their seating pattern may have been violated to a large degree!

As the impromptu peacemaker between the two factions, it is your job to reunite the Grape and Raisin factions to their former glory. To do so, you may perform a series of swaps. In any given swap, you may choose two distinct faction members (possibly from different factions), and swap their positions at the table.

Eventually, your goal is to return the table to a state such that no two members from the same faction are sitting in an adjacent manner. If that is the case, then the Grapes and the Raisin may begin peace talks and become allies once again.

You must be prepared for the worst, though. Namely, given that each faction has $$$N$$$ members, you must report the maximum number of swaps required over any possible arrangements of faction members assuming that you act optimally (that is, you always perform the minimum number of swaps).

The input will begin with a single integer, $$$Q\ (1 \leq Q \leq 10^5)$$$, denoting the number of situations you must evaluate. The next $$$Q$$$ lines will each contain a single integer, $$$N\ (1 \leq N \leq 10^{18})$$$, denoting the number of faction members of each type which are sitting around the circular table.

Your output should consist of a $$$Q$$$ integers, one per line, the $$$i$$$-th of which should denote the maximum number of required swaps over any initial arrangement of faction members around the table under the assumption that you act optimally in the $$$i$$$-th situation.

2
1
2

0
1

In the sample case, there are two situations.

In the first situation, each faction consists of a single member, meaning that no matter what arrangement they begin in, no swaps are required to return to a valid arrangement.

In the second arrangement, each faction consists of two members. In the worst case, only a single swap is required to return to a valid arrangement.