11387: Card Game

       Joe is playing a card game. There is a pile of cards numbered 1, 2, ... n from top to bottom. Every time Joe throws away the top card and puts the second card to the bottom, until there is only one card. Can you tell Joe the number of the last card?

        There are multiple test cases (no more than 1000). Each test case contains only one integer n (1 <= n <= 10^6), the number of cards.

       There is only one line for each test case, containing the last card's number.

3
6
10

2
4
4