a 채굴하기

블록체인 기술은 비트코인, 이더리움 같은 여러 디지털 화폐 시스템에서 쓰인다. 이 기술에서는 분산된 사용자들이 공통된 기록 목록(체인)을 공유하며, 사용자는 수학 문제를 풀어 체인에 새 기록을 추가할 권리를 얻는다. 이 과정을 채굴이라고 한다. i-Taiwan 회사는 ICPC(I-taiwan Coins for the Public Currency)라는 새 디지털 화폐 시스템을 개발했다. ICPC 시스템에서 채굴을 위한 수학 문제는 다음과 같다. 양의 정수 n이 주어질 때, 어떤 양의 정수 b에 대해

1/n = 1/(a⊕b) + 1/b

를 만족하는 가장 큰 정수 a를 찾아야 한다. 여기서 ⊕는 비트 단위 배타적 논리합 연산자다. 예를 들어 n = 12일 때 해는 a = 145다. 이때 b = 13이므로 a ⊕ b = 145 ⊕ 13 = 10010001₂ ⊕ 1101₂ = 10011100₂ = 156이다. 따라서

1/(a⊕b) + 1/b = 1/156 + 1/13 = 1/12 = 1/n.

여러분은 야심찬 프로그래머이고, 이 시스템에서 짧은 시간에 많은 디지털 코인을 채굴하려고 한다. ICPC의 보상을 받으려면 각 n에 대해 가장 큰 a를 구하는 프로그램을 작성하라.

입력 파일의 첫째 줄에는 테스트 케이스의 수를 나타내는 양의 정수 T가 하나 주어진다. 이어지는 T개의 줄에는 각각 하나의 테스트 케이스가 주어지며, 정수 n이 주어진다.

각 테스트 케이스마다 가장 큰 수 a를 한 줄에 출력한다.

• 1 ≤ T ≤ 20
• 0 < n ≤ 10⁷