Задана последовательность A = (A₁, A₂, …A_K) из K целых положительных чисел. На основании её получите последовательность B = (B₁, B₂, …B_K), где B_i — максимальное из чисел, полученных из A_i заменой в его двоичном представлении (без ведущих нулей) одной единички на ноль, либо одного нуля на единичку.

Input

В первой строке записано число K (1 ≤ K ≤ 10⁵). Вторая строка состоит из K чисел, не превосходящих 2³² − 1 — последовательности A (для 50 % тестов эти числа не превосходят 2¹⁶ − 1). Числа B_i также не должны превосходить этой величины.

Output

Выведите строку из K чисел — элементов последовательности B. Числа должны разделяться единственным пробелом, в начале и конце строки пробелы не допускаются.

Example

input.txt	output.txt
3 50 7 128	58 6 192