Description

Josephus problem is a game about killing people.

Suppose there are N people in a room. Their ID can be represented as #1 ,# 2 , #3 , ..... , #N

Assume #1 always have a knife at beginning of the game. and the guy with knife will kill the one next to him.

Below is a example to show how it works :

 

N = 5

First , #1 will kill #2 and give the knife to #3

Then , #3 will kill #4 and give the knife to #5

#5 will kill #1 and give the knife to #3

#3 will kill #5 and  win the game.

The question is :  Who survives in the end of the game ?  

 

Input

The first line contains a integer M, indicating the number of testcases.

You can use this format in your code:

int i , M;

scanf("%d",&M);

for(i=0;i<M;i++){

      // your code to deal with each testcase

}

The following lines are testcases.

For each testcases contains an integer N which indicate how many people joining the game.

(2<=N<=100)

Output

An integer which indicate who survives at the end of the game.

Namely , the people who win the game.

Sample Input  Download

Sample Output  Download

Tags

Discuss