Казалось бы, что общего может быть у наибольшего общего делителя и битовых операций? Самое время это выяснить.
Пусть вам дано целое положительное число \(a\). Вы хотите выбрать такое целое число \(b\) от \(1\) до \(a - 1\) включительно, чтобы наибольший общий делитель (НОД) чисел \(a \oplus b\) и \(a \> \& \> b\) был как можно больше. Иными словами, необходимо вычислить следующую функцию:
\(\)f(a) = \max_{0 < b < a}{gcd(a \oplus b, a \> \& \> b)}.\(\)
Здесь \(\oplus\) обозначает операцию побитового исключающего ИЛИ, а \(\&\) обозначает операцию побитового И.
Наибольший общий делитель двух целых чисел \(x\) и \(y\) — максимальное целое число \(g\) такое, что и \(x\), и \(y\) делится на \(g\) без остатка.
Вам дано \(q\) чисел \(a_1, a_2, \ldots, a_q\). Для каждого из этих чисел посчитайте наибольшее возможное значение наибольшего общего делителя (при оптимальном выборе \(b\)).
Выходные данные
Для каждого числа выведите ответ на него в том же порядке, в котором числа даны во входных данных.
Примечание
Для первого числа оптимально выбрать \(b = 1\), тогда \(a \oplus b = 3\), \(a \> \& \> b = 0\), наибольший общий делитель чисел \(3\) и \(0\) равен \(3\).
Для второго числа один возможный вариант — выбрать \(b = 2\), тогда \(a \oplus b = 1\), \(a \> \& \> b = 2\), наибольший общий делитель чисел \(1\) и \(2\) равен \(1\).
Для третьего числа оптимально выбрать \(b = 2\), тогда \(a \oplus b = 7\), \(a \> \& \> b = 0\), наибольший общий делитель чисел \(7\) и \(0\) равен \(7\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
2
3
5
|
3
1
7
|