이상한 섞기 연산

인덱스가 $1$부터 시작하는 길이 $n$의 수열 $B$가 있으며, 초기에 모든 인덱스 $k$에 대해 $B_k=k$입니다. 흐즈로는 이 수열에 할 수 있는 매우 이상하고 신기한 연산을 생각해 냈습니다. 그 연산은 다음과 같습니다.

• 어떠한 양의 정수 $k$가 주어질 때, $k$의 약수인 가장 큰 $2$의 거듭제곱수 $l$을 찾고, $k \neq l$이라면 $B_k$와 $B_l$을 서로 교환하는 동작을 $k$-교환이라고 합시다.
• $i$-교환을 $i=1,2,\cdots,n$에 대해 순서대로 반복합니다.

흐즈로는 이 연산을 이상한 섞기 연산이라고 부르기로 했습니다. 수열 $B$의 길이 $n$이 주어질 때, $B$에 이상한 섞기 연산을 수행한 뒤 원소 $1$이 있는 인덱스를 출력하세요. 다시 말해, 연산이 끝난 후 $B_j=1$이 되는 인덱스 $j$를 찾아 출력해야 합니다.

첫 번째 줄에 테스트 케이스의 개수 $T$가 주어집니다. ($1 \le T \le 1000$)

그다음 줄부터 총 $T$개의 줄에 각각 $B$의 길이를 나타내는 정수 $n$이 한 줄에 하나씩 주어집니다. ($1 \le n \le 10^9$)

각 테스트 케이스에 대해, 길이가 $n$인 수열 $B$에 이상한 섞기 연산을 수행한 뒤 원소 $1$이 있는 인덱스 $j$를 별도의 줄에 출력하세요.

본 문제에서 $2$의 거듭제곱수는 $2^k$ 꼴로 표현했을 때 $k$가 음이 아닌 정수가 되는 수로 정의됩니다.