#1532 카드 섞기

84  1 s   128 MB  

Description

카드게임을 할 때, 우리는 대체로 매 게임이 끝날 때마다 카드를 섞는다.
카드를 섞는 방법 중 리플 셔플이라는 방법이 있는데 리플 셔플이란 먼저 카드를 두 뭉치로 나눈 다음 두 뭉치의 카드가 서로 엇갈리게 하여 카드를 섞는것을 뜻한다.

예를 들어 1부터 10까지의 카드가 순차적으로 정렬되어 있다고 할 때 이 카드를 1번 리플 셔플하면

1 2 3 4 5 6 7 8 9 10
에서
1 3 5 7 9 2 4 6 8 10
이 된다.

카드를 섞는 횟수 N이 주어질 때 순차적으로 정렬되어 있는 10개의 카드를 N번 리플 셔플한 결과값을 구하는 프로그램을 작성하라.

Input

맨 처음 테스트 케이스의 수 T가 들어온다.
그 다음 T만큼 리플 셔플의 횟수 N이 입력으로 들어온다.
( 1 <= T <= 100, 0 <= N <= 2,147,483,647 )

Output

N번의 리플 셔플을 거친 후의 카드의 순서를 출력한다.

Sample Input

Sample Output

2
1
2
1 3 5 7 9 2 4 6 8 10
1 5 9 4 8 3 7 2 6 10

Source

From Arshuaz