Veider funktsioon

시간 제한0.1초메모리 제한1024 MB

요약

각 A에 대해 1 이상 A 미만인 b를 골라 gcd(A XOR b, A AND b)를 최대화하고 그 값을 출력한다.

난이도: 어려움10점 중 8점
유형: 비트 연산, 수학, 정수론
정답자: 아직 제출이 없습니다

문제

On antud positiivne täisarv $a$ . Vaja on valida täisarv $b$ ( $1 \le b \le a - 1$ ) nii, et arvude $a \oplus b$ ja $a \otimes b$ suurim ühistegur oleks maksimaalne võimalik, ja väljastada see ühistegur. Teisisõnu on vaja leida funktsiooni $f(a) = \max\_{0\<b\<a} \gcd(a \oplus b, a \otimes b)$ väärtus $f(A)$ , kus $\oplus$ tähistab tehet "bitikaupa välistav VÕI" ja $\otimes$ tehet "bitikaupa JA". Nende tehete väärtused ühebitistel arvudel on:

$a$	$b$	$a \oplus b$	$a \otimes b$
0	0	0	0
0	1	1	0
1	0	1	0
1	1	0	1

Pikematele arvudele rakendatakse neid tehteid nii, et vaadeldakse operandide kahendesitusi, sooritatakse tehted nende vastavate bittide vahel ja saadud tulemused moodustavad vastuse kahendesituse. Mõned näited:

Tehe 10-süsteemis	Tehe 2-süsteemis	Tulemus 2-süsteemis	Tulemus 10-süsteemis
$5 \oplus 3$	$101 \oplus 11$	$110$	$6$
$5 \otimes 3$	$101 \otimes 11$	$1$	$1$
$7 \oplus 42$	$111 \oplus 101010$	$101101$	$45$
$7 \otimes 42$	$111 \otimes 101010$	$10$	$2$

입력

Faili esimesel real on päringute arv $N$ ( $1 \le N \le 1\\,000$ ) ja järgmisel $N$ real igaühel üks täisarv $A\_i$ ( $2 \le A\_i < 2^{25}$ ).

출력

Faili väljastada $N$ rida. Faili reale number $i$ väljastada $f(A\_i)$ väärtus.

예제1

예제 1
입력
```
3
2
3
5
```
예상 출력
```
3
1
7
```