Штирлиц получил от штаба T чисел. «Шифровка», — подумал Мюллер. «Простые числа», — подумал Штирлиц. Но не всё так просто!

Для шифрования штаб использует побитовое исключающее «ИЛИ». Пусть есть два числа, представим их в двоичной записи. Тогда результатом этой операции будет число, каждый бит двоичной записи которого является результатом исключающего «ИЛИ» соответствующих позиций у данных двух чисел: для битов «0» и «0» или битов «1» и «1» результат равен «0», а для битов «0» и «1» или «1» и «0» — результат равен «1». Например, результатом побитового исключающего «ИЛИ» и у чисел 1001₂ и 0101₂ будет 1100₂.

Штаб берёт простое число и другое неотрицательное целое число (ключ шифрования), использует побитовое исключающее «ИЛИ» между ними, и таким образом получает результат. При этом ключи шифрования могут быть разными для разных чисел. Но есть одна проблема — Штирлиц забыл ключи шифрования штаба и поэтому не может расшифровать ни одно из чисел! Но, немного подумав, Штирлиц догадался, что может применить используемую штабом операцию ещё раз, чтобы получить простые числа. Теперь для каждого из чисел в послании ему нужно найти минимальный возможный ключ, операция с которым приведёт его к простому числу.

Мюллер уже на носу, поэтому Штирлиц попросил у Вас помощи с таким важным заданием.

В первой строке дано целое число T — количество чисел в послании от штаба (1 ≤ T ≤ 10⁵).

В следующих T строках дано по одному целому числу a_i — числа из послания (0 ≤ a_i ≤ 1 048 575).

Выведите T неотрицательных целых чисел, каждое в новой строке — наименьший ключ шифрования для каждого из зашифрованных чисел в порядке ввода.