On a planet called RUIZ LAND, which is ruled by the queen, Erika Ruiz. Each person on that planet has a strength value (strength value >0).
That planet has a special rule made by the queen that a boy and a girl will form a couple if their Hate value is a prime number where $Hate$ is given by the formula:-
Hate = (boy's strength value)  XOR (girl's strength value )
You are given $N$ numbers denoting the strength value of $N$ girls, and each of the $N$ girls has to form a couple with a boy such that sum of $Hate$ value of all the $N$ couples will be minimum.
You need to print the strength value of each boy, Where the boy at index $i$ will form a couple with the girl at index $i$, where $1 \leq i \leq N$.
Assume that you can always find at least one boy having that strength for each girl.

-----Input:-----
- First line will contain $N$, the number of Girls. 
- Next line contains $N$ numbers separated by space denoting strength value for each girl.

-----Output:-----
Print the required $N$ numbers denoting strength of boys.

-----Constraints-----
- $1 \leq N \leq 100000$
- $1 \leq A_i \leq 10^9$ , (where $1 \leq i \leq N$) and $A_i$ denotes strength of i'th girl.

-----Sample Input:-----
2
10 16

-----Sample Output:-----
8 18

Difficulty: interview

Starter code:

Solutions:
n=int(input())
a=list(map(int,input().split()))
c=[]
for i in range(len(a)):
    if a[i]==2:
        c.append(1)
    else:
        c.append(a[i]^2)
print(*c)

import copy
n=int(input())
a=list(map(int,input().split()))
c=[]
for i in range(len(a)):
    if a[i]==2:
        c.append(1)
    else:
        str=bin(a[i])[2:]
        if len(str)!=32:
            rem=32-len(str)
            str='0'*rem+str
        str1=copy.deepcopy(str)
        str1=list(x for x in str1)

        if str[31]=='0':
             str1[31]='0'
        if str[31]=='1':
            str1[31]='1'
        if str[30]=='0':
            str1[30]='1'
        if str[30]=='1':
            str1[30]='0'
        ##print(str1)
        str1=''.join(str1)
        x=int(str1,2)
        c.append(x)
print(*c)

# cook your dish here
n=int(input())
l=list(map(int,input().split()))
for i in l:
    if i==1:
        print(3,end=' ')
        continue
    if i==2:
        print(1,end=' ')
        continue
    s=list(bin(i)[2:])
    if s[-2]=='1':
        s[-2]='0'
    else:
        s[-2]='1'
    x=int(''.join(s),2)
    print(x,end=' ')
print()


n=int(input())
a=list(map(int,input().rstrip().split()))
ans=[]
for i in a:
    if i==2:
        ans.append(1)
    else:
        ans.append(i^2)
print(*ans)


lens = int(input())
arrs = [int(x) for x in input().split()]
vals = []
for a in arrs:
    if a != 2:
        vals.append(2 ^ a)
    else:
        vals.append(3 ^ a)
print(*vals)

n=int(input())
l=list(map(int,input().split()))
ans=[]
for i in l:
    if i==2:
        ans.append(1)
    else:
        ans.append(i^2)
print(*ans)

n=int(input())
l=list(map(int,input().split()))
ans=[]
for i in l:
    if i==2:
        ans.append(1)
    else:
        ans.append(i^2)
print(*ans)

from sys import stdin, stdout
from math import floor, gcd, fabs, factorial, fmod, sqrt, inf, log
from collections import defaultdict as dd, deque
from heapq import merge, heapify, heappop, heappush, nsmallest
from bisect import bisect_left as bl, bisect_right as br, bisect
mod = pow(10, 9) + 7
mod2 = 998244353
def inp(): return stdin.readline().strip()
def out(var, end="\n"): stdout.write(str(var)+"\n")
def outa(*var, end="\n"): stdout.write(' '.join(map(str, var)) + end)
def lmp(): return list(mp())
def mp(): return map(int, inp().split())
def smp(): return map(str, inp().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]
def remadd(x, y): return 1 if x%y else 0
def ceil(a,b): return (a+b-1)//b

def isprime(x):
    if x<=1: return False
    if x in (2, 3): return True
    if x%2 == 0: return False
    for i in range(3, int(sqrt(x))+1, 2):
        if x%i == 0: return False
    return True
    
n = int(inp())
arr = lmp()
for i in range(n):
    if arr[i]==2:
        print(1, end=" ")
    elif arr[i]^2<arr[i]:
        print(arr[i]-2, end=" ")
    else:
        print(arr[i]+2, end=" ")
print()
    

# cook your dish here
n=int(input())
a=[int(i) for i in input().split()]
for i in a:
    if i==1:
        print("2",'',end='')
    elif i==2:
        print("1",'',end='')
    else:
        b=str(bin(i)).replace('0b','')
        p=''
        l=len(b)
        if b[l-1]=='0':
            p='0'
        else:
            p='1'
        if b[l-2]=='0':
            p='1'+p
        else:
            p='0'+p
        for j in range(l-3,-1,-1):
            p=b[j]+p
        print(int(p,2),'',end='')
print()

# cook your dish here
# cook your dish here
def solve():
  k = int(input())
    #n,m = input().split()
    #n = int(n)
    #m = int(m)
    #s = input()
  a = list(map(int, input().split()))
  #print(a)
  for i in range(k):
    n2=-1
    if a[i]==1 :n2 =3
    elif a[i]==2 :n2 =1
    else:
      b = bin(a[i]).replace("0b","")
      n = len(b)
      #print(b)
      if b[n-2]=='0': b=b[0:n-2]+'1'+b[n-1:]
      else: b=b[0:n-2]+'0'+b[n-1:]
      #print(b)
      n2 = int(b,2)
    #print(n2)
    if i==k-1:print(n2,end="")
    else: print(n2,end=" ")
        
            
    
    
def __starting_point():
    #T = int(input())
    #for i in range(T):
        #a = solve()
        #n = len(a)
        #for i in range(n):
         #   if i==n-1 : print(a[i])
          #  else: print(a[i],end=" ")
        (solve())
__starting_point()

# cook your dish here
n = int(input())
arr = list(map(int,input().split()))
for i in arr:
	if i == 2:
		print("1",end=" ")
	else:
		print(i^2,end=" ")

def func(lst):
    for i in lst:
        if i == 2:
            print(i^3, end=' ')
        else:
            print(i^2, end=' ')


n = int(input())
lst = list(map(int, input().split()))
func(lst)



n=int(input())
b=list(map(int,input().split()))
res=[]
for j in range(n):
    if b[j]!=2:
        res.append(b[j]^2)

    else:
        res.append(b[j]^3)

print(*res)

# author : Tapan Goyal
#           MNIT Jaipur

import math
import bisect
import itertools
import sys
I=lambda : sys.stdin.readline()
one=lambda : int(I())
more=lambda : map(int,I().split())
linput=lambda : list(more())

mod=10**9 +7
inf=10**18 + 1 

'''fact=[1]*100001
ifact=[1]*100001
for i in range(1,100001):
    fact[i]=((fact[i-1])*i)%mod
    ifact[i]=((ifact[i-1])*pow(i,mod-2,mod))%mod
def ncr(n,r):
    return (((fact[n]*ifact[n-r])%mod)*ifact[r])%mod
def npr(n,r):
    return (((fact[n]*ifact[n-r])%mod))
    '''


def merge(a,b):
    i=0;j=0
    c=0
    ans=[]
    while i<len(a) and j<len(b):
        if a[i]<b[j]:
            ans.append(a[i])
            i+=1
        else:
            ans.append(b[j])
            c+=len(a)-i
            j+=1
    ans+=a[i:]
    ans+=b[j:]
    return ans,c
def mergesort(a):
    if len(a)==1:
        return a,0
    mid=len(a)//2   
    left,left_inversion=mergesort(a[:mid])
    right,right_inversion=mergesort(a[mid:])
    m,c=merge(left,right)
    c+=(left_inversion+right_inversion)
    return m,c
    
def is_prime(num):
    if num == 1: return False
    if num == 2: return True
    if num == 3: return True
    if num%2 == 0: return False
    if num%3 == 0: return False
    t = 5
    a = 2
    while t <= int(math.sqrt(num)):
        if num%t == 0: return False
        t += a
        a = 6 - a
    return True

  
def ceil(a,b):
    return (a+b-1)//b
    


#/////////////////////////////////////////////////////////////////////////////////////////////////
def __starting_point():
    for _ in range(1):
        n=one()
        a=linput()
        for i in a:
            ans=i^2
            if ans>0:
                print(ans,end=" ")
            else:
                print(i^3,end=" ")
                
            
__starting_point()

# cook your dish here
n=int(input())
a=list(map(int,input().split()))
b=[]
for i in range (n):
    num=a[i]
    b.append(num)
    num//=2
    if num%2==1:
        b[i]-=2
    else:
        b[i]+=2
    if b[i]==0:
        b[i]=1
print(*b)

# cook your dish here
n=int(input())
arr=list(map(int,input().split()))
for x in arr:
    if x==2:
        print(end='1 ')
    else:
        y=x%4
        if y>1:
            print(x-2,end=' ')
        else:
            print(x+2,end=' ')
print()


n = int(input())
a = list(map(int, input().split()))

for i in a:
    if i != 2:
        print(i^2, end=' ')
    else:
        print(1, end=' ')

print()


# cook your dish here
n = int(input())
arr = [int(s) for s in input().split(" ")]
ans = []
for x in arr:
    if x == 2:
        ans.append(1)
    else:
        ans.append(x^2)
print(*ans)

n = int(input())

def foo(n):
    if int(n)==2:
        return str(2^3)
    return str(int(n)^2)

data = list(map(foo, input().split()))

print(' '.join(data))


import sys
def get_ints(): return map(int, sys.stdin.readline().strip().split())
def get_int(): return list(map(int, sys.stdin.readline().strip().split()))[0]
def get_list(): return list(map(int, sys.stdin.readline().strip().split()))
def get_string(): return sys.stdin.readline().strip()

N = 0
a = []

def solve():
    nonlocal N
    N = get_int()
    a = get_list()
    for i in a:
        if i == 2:
            print(1, end=' ')
        else:
            print(i ^ 2, end=' ')
    print()

test_cases = 1 # get_int()

for _ in range(test_cases):
    solve()


from sys import stdin, stdout
# #from collections import Counter
# n = int(stdin.readline())
# #l = list(map(int, stdin.readline().split()))
# #l = [int(stdin.readline()) for _ in range(n)]
# #a, b = input().split()
# for _ in range(n):
n1 = int(stdin.readline())
l = list(map(int, stdin.readline().split()))
for x in l:
    if x!=2:
        print(x^2,end=' ')
    else:
        print(1,end=' ')
print()

n=int(input())
l=list(map(int,input().split()))
ans=[]
for i in l:
    x=i^2
    if x==0:
        ans.append(i^3)
    else:
        ans.append(x)
print(*ans)