Can the greatest common divisor and bitwise operations have anything in common? It is time to answer this question.

Suppose you are given a positive integer a. You want to choose some integer b from 1 to a - 1 inclusive in such a way that the [greatest common divisor (GCD)](https://en.wikipedia.org/wiki/Greatest_common_divisor) of integers a ⊕ b and a \> \& \> b is as large as possible. In other words, you'd like to compute the following function:

$$$f(a) = max_{0 < b < a}{gcd(a ⊕ b, a \> \& \> b)}.$$$

Here ⊕ denotes the [bitwise XOR operation](https://en.wikipedia.org/wiki/Bitwise_operation#XOR), and \& denotes the [bitwise AND operation](https://en.wikipedia.org/wiki/Bitwise_operation#AND).

The greatest common divisor of two integers x and y is the largest integer g such that both x and y are divided by g without remainder.

You are given q integers a_1, a_2, …, a_q. For each of these integers compute the largest possible value of the greatest common divisor (when b is chosen optimally). 

Input

The first line contains an integer q (1 ≤ q ≤ 10^3) — the number of integers you need to compute the answer for.

After that q integers are given, one per line: a_1, a_2, …, a_q (2 ≤ a_i ≤ 2^{25} - 1) — the integers you need to compute the answer for. 

Output

For each integer, print the answer in the same order as the integers are given in input.

Example

Input


3
2
3
5


Output


3
1
7

Note

For the first integer the optimal choice is b = 1, then a ⊕ b = 3, a \> \& \> b = 0, and the greatest common divisor of 3 and 0 is 3.

For the second integer one optimal choice is b = 2, then a ⊕ b = 1, a \> \& \> b = 2, and the greatest common divisor of 1 and 2 is 1.

For the third integer the optimal choice is b = 2, then a ⊕ b = 7, a \> \& \> b = 0, and the greatest common divisor of 7 and 0 is 7.
	import java.util.*;
	import java.io.*;
	import java.lang.reflect.Array;
	
			public class codeforces
			{	
				public static void main(String[] args)
				{
					InputReader in = new InputReader(System.in);
					PrintWriter pw = new PrintWriter(System.out);
	
						int q = in.nextInt();
						
						while(q-- > 0)
						{
							long n = in.nextLong();
							int count = 0, t_count = 0, temp = 0;
							long ans = 1, t_ans = 0;
							
							while(n > 0)
							{
								if(n%2 == 1)
									count++;
								
								n /= 2;
								t_count++;
							}
							
							temp = t_count;
							
							while(temp-- > 0)
								ans *= 2;
							
							ans--;
							
							t_ans = ans;
							
							if(t_count == count)
							{
								ans = 1;
								
								for(int i=2;i*i<=t_ans;i++)
								{
									if(t_ans%i == 0)
									{
										ans = t_ans/i;
										break;
									}
								}
							}
							
							pw.println(ans);
						}
						
					pw.flush();
					pw.close();
				}
				
				public static long fact(long n, long M)
				{
					long ans = 1;
					
					for(long i=n;i>0;i--)
					{
						ans = (ans*i)%M;
					}
					
					return ans;
				}
				
			/*	public static void DFS(int sourse)
				{
					int count = 0;
					visited[sourse] = true;
					
					for(int u : adj[sourse])
					{
						if(!visited[u])
						{
							DFS(u);
						}
					}
					
					
				}*/
				
				public static ArrayList Divisors(int n)
				{
				    ArrayList<Integer> div = new ArrayList<>();
				    
				    for (int i=1; i<=Math.sqrt(n); i++)
				    {
				        if (n%i == 0)
				        {
				        	div.add(i);
				                
				            if(n/i != i)
				            	div.add(n/i);
				        }
				    }
				    return div;
				}
			
				public static int BinarySearch(long[] a, long k)
				{
					int n = a.length;
					int i = 0, j = n-1;
					int mid = 0;
					
					if(k < a[0])
						return 0;
					else if(k >= a[n-1])
						return n;
					else
					{
						while(j - i > 1)
						{
							mid = (i+j)/2;
							
							if(k >= a[mid])
								i = mid;
							else
								j = mid;
						}
					}
					
					return i+1;
				}
				public static long GCD(long a,long b)
				{
					if(b==0)
						return a;
					else
						return GCD(b,a%b);
				}
				
				public static long LCM(long a,long b)
				{
					return (a*b)/GCD(a, b);
				}
				
				static class pair implements Comparable<pair>
				{
					Integer x, y;
					pair(int x,int y)
					{
						this.x=x;
						this.y=y;
					}
					
					public int compareTo(pair o) {
						int result = x.compareTo(o.x);
						if(result==0)
							result = y.compareTo(o.y);
						
						return result;
					}  
					
					public String toString()
					{
						return x+" "+y;
					}
					
					public boolean equals(Object o)
					{
						if (o instanceof pair)
					    {
							pair p = (pair)o;
							return p.x - x == 0 && p.y - y == 0 ;
						}
						return false;
					}
					
					public int hashCode()
					{
						return new Long(x).hashCode()*31 + new Long(y).hashCode();
					}
				}
				
				static class InputReader 
				{
					 
					private final InputStream stream;
					private final byte[] buf = new byte[8192];
					private int curChar, snumChars;
					private SpaceCharFilter filter;
			 
					public InputReader(InputStream stream) 
					{
						this.stream = stream;
					}
			 
					public int snext() 
					{
						if (snumChars == -1)
							throw new InputMismatchException();
						if (curChar >= snumChars) 
						{
							curChar = 0;
							try 
							{
								snumChars = stream.read(buf);
							} 
							catch (IOException e) 
							{
								throw new InputMismatchException();
							}
							if (snumChars <= 0)
								return -1;
						}
						return buf[curChar++];
					}
			 
					public int nextInt() 
				    {
						int c = snext();
						while (isSpaceChar(c)) 
						{
							c = snext();
						}
						int sgn = 1;
						if (c == '-')
					    {
							sgn = -1;
							c = snext();
						}
						int res = 0;
						do 
						{
							if (c < '0' || c > '9')
								throw new InputMismatchException();
							res *= 10;
							res += c - '0';
							c = snext();
						} while (!isSpaceChar(c));
						return res * sgn;
					}
			 
					public long nextLong()
				    {
						int c = snext();
						while (isSpaceChar(c)) 
						{
							c = snext();
						}
						int sgn = 1;
						if (c == '-') 
						{
							sgn = -1;
							c = snext();
						}
						long res = 0;
						do 
						{
							if (c < '0' || c > '9')
								throw new InputMismatchException();
							res *= 10;
							res += c - '0';
							c = snext();
						} while (!isSpaceChar(c));
						return res * sgn;
					}
			 
					public int[] nextIntArray(int n) 
					{
						int a[] = new int[n];
						for (int i = 0; i < n; i++) 
						{
							a[i] = nextInt();
						}
						return a;
					}
			 
					public String readString()
				    {
						int c = snext();
						while (isSpaceChar(c)) 
						{
							c = snext();
						}
						StringBuilder res = new StringBuilder();
						do 
						{
							res.appendCodePoint(c);
							c = snext();
						} while (!isSpaceChar(c));
						return res.toString();
					}
			 
					public String nextLine() 
					{
						int c = snext();
						while (isSpaceChar(c))
							c = snext();
						StringBuilder res = new StringBuilder();
						do 
						{
							res.appendCodePoint(c);
							c = snext();
						} while (!isEndOfLine(c));
						return res.toString();
					}
			 
					public boolean isSpaceChar(int c) 
					{
						if (filter != null)
							return filter.isSpaceChar(c);
						return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
					}
			 
					private boolean isEndOfLine(int c) 
					{
						return c == '\n' || c == '\r' || c == -1;
					}
			 
					public interface SpaceCharFilter
				    {
						public boolean isSpaceChar(int ch);
					}
				}
				
				static class CodeX {
		        public static void sort(long arr[]) {
		            merge_sort(arr, 0, arr.length - 1);
		        }
		
		        private static void merge_sort(long A[], long start, long end) {
		            if (start < end) {
		                long mid = (start + end) / 2;
		                merge_sort(A, start, mid);
		                merge_sort(A, mid + 1, end);
		                merge(A, start, mid, end);
		            }
		
		        }
		
		        private static void merge(long A[], long start,long mid, long end) {
		            long p = start, q = mid + 1;
		            long Arr[] = new long[(int)(end - start + 1)];
		            long k = 0;
		
		            for (int i = (int)start; i <= end; i++) {
		                if (p > mid)
		                    Arr[(int)k++] = A[(int)q++];
		
		                else if (q > end)
		                    Arr[(int)k++] = A[(int)p++];
		
		                else if (A[(int)p] < A[(int)q])
		                    Arr[(int)k++] = A[(int)p++];
		
		                else
		                    Arr[(int)k++] = A[(int)q++];
		            }
		            for (int i = 0; i < k; i++) {
		                A[(int)start++] = Arr[i];
		            }
		
		        }
		
		    }
			}	
			
	
				