FF has dogs numbered . At the beginning, the dogs are arranged by their number in ascending order. They are playing a swapping game, the rules of game are as follows:

1. The dogs will swap in every second.

2. If the current number of seconds is odd, then swap the dog which index is and . For example, if , the sequence of dogs is and the current time at the beginning(current time is 1), then the dogs will be after 1-st second.

3. If the current number of seconds is even, then swap the dog which index is and . For example, if , the sequence of dogs is and the current time is 2, then the dogs will be after 2-nd seconds.

FF wants to know, what is the index of the dog numbered after seconds.

The input consists of multiple test cases. The first line contains an integer  --- the number of test cases. The description of the test cases follows.

The only line of each test case contains three integer .

Print  lines for test cases, and every line contains one integer means the index of the dog after swapping.

3
5 1 3
5 2 3
6 1 4

4
5
3

In first case, there are 5 dogs at the beginning, and the sequence of dogs is . After 1 second,the sequence is , now the dog numbered 3 is in index 4.