Problem: You have been blessed as a child of Omkar. To express your gratitude, please solve this problem for Omkar!

An array a of length n is called complete if all elements are positive and don't exceed 1000, and for all indices x,y,z (1 ≤ x,y,z ≤ n), a_{x}+a_{y} ≠ a_{z} (not necessarily distinct).

You are given one integer n. Please find any complete array of length n. It is guaranteed that under given constraints such array exists.

Input

Each test contains multiple test cases. The first line contains t (1 ≤ t ≤ 1000) — the number of test cases. Description of the test cases follows.

The only line of each test case contains one integer n (1 ≤ n ≤ 1000).

It is guaranteed that the sum of n over all test cases does not exceed 1000.

Output

For each test case, print a complete array on a single line. All elements have to be integers between 1 and 1000 and for all indices x,y,z (1 ≤ x,y,z ≤ n) (not necessarily distinct), a_{x}+a_{y} ≠ a_{z} must hold.

If multiple solutions exist, you may print any.

Example

Input


2
5
4


Output


1 5 3 77 12
384 384 44 44

Note

It can be shown that the outputs above are valid for each test case. For example, 44+44 ≠ 384.

Below are some examples of arrays that are NOT complete for the 1st test case:

[1,2,3,4,5] 

Notice that a_{1}+a_{2} = a_{3}.

[1,3000,1,300,1] 

Notice that a_{2} = 3000 > 1000.

Solution (in JAVA):

Solution:
   
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.lang.*;
 
public class test
{ static final long modp =1000000007;
    static long x_ec=1,y_ec=0,d_ec =1;
    static long maxi=0;
    static boolean v1 =false ,v2 = false;
  

    public static void main(String args[])
    { InputReader in = new InputReader(System.in);
        OutputStream outputStream = System.out;
        OutputWriter out = new OutputWriter(outputStream);

        int e=in.readInt();
        for(int i=0;i<e;i++)
        {int n= in.readInt();
            int j=1;
            for(;j<n;j+=2)
            { out.print(j+" "+j+" ");

            }
            if(n%2!=0)
            out.println(j);
            else
            out.println("");

        }
       

           
    out.close(); 
      
 }
/*
//returns rightmost one in binary representation in x
 static long rightmostone(long x)
 {return (x &(-x));
 }
//  Returns the number x with the nth bit set.
static long nthset(long x ,long n)
 {return (x|1<< n);
 }

*/
static Node lca(Node root,int x,int y)
{if(root==null)
    return null;
    if(root.value>x &&root.value>y )
    return lca(root.left, x, y);
     if(root.value<x &&root.value<y )
    return lca(root.right, x, y);

    return root;
}




static Node common(Node root,int x,int y)
{  if(root==null)
    return null;
    Node temp=null;
    if(root.value ==x)
    { v1= true;
        temp =new Node(x);

    }
    else if(root.value ==y)
    { v2= true;
        temp =new Node(y);

    }
  Node  lef =common(root.left, x, y);
 Node rig =common(root.right, x, y);
   if(temp!=null)
   return temp;
   if(lef ==null)
   return rig;
   if(rig==null)
   return lef;
   return root;
}

// static class Node {
//     int value;
//     Node left;
//     Node right;
    
//     Node(int value){
//         this.value =value;
//         right =null;
//         left =null;
//     }
// }
static Node insert(Node root,int v)
  { if(root==null)
    return new Node(v);
      if( v<=root.value)
      root.left =insert(root.left, v);
      else
      root.right =insert(root.right,v);

      return root;

    }
  
  static int minvalue(Node root)
    {
        while(root.left!=null)
          root =root.left;
          return root.value;

        

    }
    static Node delete(Node root ,int val)
 { if(root ==null)
    return root;
    if(val<root.value)
    root.left=delete(root.left, val);
   else if(val>root.value)
   root.right =delete(root.right,val);
   else {
   if(root.left==null)
     return root.right;
     else if(root.right==null)
     return root.left;
     root.value= minvalue(root.right);
     root.right =delete(root.right, root.value);
   

   }
   return root;


 }
 static void inorder(Node root,OutputWriter out)
 { if(root!=null)
   {inorder(root.left ,out);
      out.print(root.value+" ");
      inorder(root.right, out);

   }
 }
 static void preorder(Node root ,OutputWriter out)
 { if(root!=null)
   { out.println(root.value+" ");
      preorder(root.left, out);
      preorder(root.right,out);

   }

 }
 static void postorder(Node root,OutputWriter out)
 { if(root!=null)
   { postorder(root.left, out);
       postorder(root.right ,out);
       out.print(root.value+" ");
   }

 }
 
// Input: Indices Range [0..size]
// Invariant: A[l] <= key and A[r] > key 
static long modExponential(long x,long n)
    {long result =1l;
        while(n>0l)
        { if(n%2==1)
            result =(x*result)%modp;
            x= (x*x)%modp;
         n=n/2;
        }
        return result;
    }
  
static int GetRightPosition(int A[], int l, int r, int key) 
{ 
    int m; 

    while( r - l > 1 ) 
    { 
        m = l + (r - l)/2; 

        if( A[m] <= key ) 
            l = m; 
        else
            r = m; 
    } 

    return l; 
} 

// Input: Indices Range -1 to size-1
// Invariant: A[r] >= key and A[l] > key 
static int GetLeftPosition(int A[], int l, int r, int key) 
{ 
    int m; 

    while( r - l > 1 ) 
    { 
        m = l + (r - l)/2; 

        if( A[m] >= key ) 
            r = m; 
        else
            l = m; 
    } 

    return r; 
} 



public static long gcd(long a,long b)
{
    if(b==0)
        return a;
    else
        return gcd(b,a%b);
}
public static int gcd(int a,int b)
{
    if(b==0)
        return a;
    else
        return gcd(b,a%b);
}
public static int abs(int a,int b)
{
    return (int)Math.abs(a-b);
}
public static long abs(long a,long b)
{
    return (long)Math.abs(a-b);
}
public static int max(int a,int b)
{
    if(a>b)
        return a;
    else
        return b;
}
public static int min(int a,int b)
{
    if(a>b)
        return b;
    else 
        return a;
}
public static long max(long a,long b)
{
    if(a>b)
        return a;
    else
        return b;
}
public static long min(long a,long b)
{
    if(a>b)
        return b;
    else 
        return a;
}
 
/*
void countsort(int arr[],int n,int place)
{
        int i,freq[range]={0};         //range for integers is 10 as digits range from 0-9
        int output[n];
        for(i=0;i<n;i++)
                freq[(arr[i]/place)%range]++;
        for(i=1;i<range;i++)
                freq[i]+=freq[i-1];
        for(i=n-1;i>=0;i--)
        {
                output[freq[(arr[i]/place)%range]-1]=arr[i];
                freq[(arr[i]/place)%range]--;
        }
        for(i=0;i<n;i++)
                arr[i]=output[i];
}
void radixsort(ll arr[],int n,int maxx)            //maxx is the maximum element in the array
{
        int mul=1;
        while(maxx)
        {
                countsort(arr,n,mul);
                mul*=10;
                maxx/=10;
        }
}*/

/* BufferedReader bf =new BufferedReader (new InputStreamReader(System.in));
        int t= Integer.parseInt(bf.readLine());
        StringBuffer gh =new StringBuffer("");
        StringTokenizer  tk=new StringTokenizer(bf.readLine());
        long a= Long.parseLong(tk.nextToken());
*/


static class Pair implements Comparable<Pair>
{
    int a,b;
    Pair (int a,int b)
    {
        this.a=a;
        this.b=b;
    }
 
    public int compareTo(Pair o) {
        
        if(this.a!=o.a)
        return Integer.compare(this.a,o.a);
        else
            return Integer.compare(this.b, o.b);
        //return 0;
    }
    public boolean equals(Object o) {
        if (o instanceof Pair) {
            Pair p = (Pair)o;
            return p.a == a && p.b == b;
        }
        return false;
    }


    public int hashCode(Object o) {
        Pair p = (Pair)o;
        return p.a* 31 +p.b;
    }

} 

//public void solve(int testNumber, InputReader in, OutputWriter out) 

// in case u want to print And take input inside and static method
static void extendedEuclid( long A,  long B) {
    if(B==0)
    {d_ec=A;
      x_ec =1;
      y_ec=0;
  
    }
    else{
        extendedEuclid(B, A%B);
         long temp =x_ec;
        x_ec = y_ec;
        y_ec =temp -(A/B)*y_ec;
    }
      
  }
  static long modInverse( long A,  long M) //A and M are coprime i.e. Ax+My=1. In the extended Euclidean algorithm, x is the modular multiplicative inverse of A under modulo M.
  {
      extendedEuclid(A,M);
      return (x_ec%M+M)%M;    //x may be negative
  }
  
  static boolean checkprime(int N) {
      int count = 0;
      for( int i = 1;i * i <=N;++i ) {
           if( N % i == 0) {
               if( i * i == N )
                       count++;
               else       // i < sqrt(N) and (N / i) > sqrt(N)
                       count += 2;
            }
      }
      if(count == 2)
           return true;
      else
        return false;
  }
  static void factorize (long a,HashMap<Long,Long> map)
    {
      long i=2;
      for( i=2;i*i<=a;i++)
      {
        if(a%i==0){
            long f=0;  
        while((a>0)&&(a%i==0))
        { 
            a= a/i;
            f++;
        }
        map.put(i, f);
      
        }
      }
      if(a>1l)
        map.put(a, 1l);

    }
    


}
class OutputWriter {
    private final PrintWriter writer;

    public OutputWriter(OutputStream outputStream) {
        writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
    }

    public OutputWriter(Writer writer) {
        this.writer = new PrintWriter(writer);
    }

    public void print(Object... objects) {
        for (int i = 0; i < objects.length; i++) {
            if (i != 0) {
                writer.print(' ');
            }
            writer.print(objects[i]);
        }
    }

    public void println(Object... objects) {
        print(objects);
        writer.println();
    }

    public void close() {
        writer.close();
    }

} 

  class InputReader
{
    private InputStream stream;
    private byte[] buf = new byte[1024];
    private int curChar;
    private int numChars;
    private SpaceCharFilter filter;
 
    public InputReader(InputStream stream)
    {
        this.stream = stream;
    }
 
    public int read()
    {
        if (numChars == -1)
            throw new InputMismatchException();
        if (curChar >= numChars)
        {
            curChar = 0;
            try
            {
                numChars = stream.read(buf);
            } catch (IOException e)
            {
                throw new InputMismatchException();
            }
            if (numChars <= 0)
                return -1;
        }
        return buf[curChar++];
    }
 
    public int readInt ()
    {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        int sgn = 1;
        if (c == '-')
        {
            sgn = -1;
            c = read();
        }
        int res = 0;
        do
        {
            if (c < '0' || c > '9')
                throw new InputMismatchException();
            res *= 10;
            res += c - '0';
            c = read();
        } while (!isSpaceChar(c));
        return res * sgn;
    }
 
    public String readString ()
    {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        StringBuilder res = new StringBuilder();
        do
        {
            res.appendCodePoint(c);
            c = read();
        } while (!isSpaceChar(c));
        return res.toString();
    }
    public String readLine() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        StringBuilder res = new StringBuilder();
        do {
            res.appendCodePoint(c);
            c = read();
        } while (!isEndOfLine(c));
        return res.toString();
    }
    
 
    public double readDouble() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        int sgn = 1;
        if (c == '-') {
            sgn = -1;
            c = read();
        }
        double res = 0;
        while (!isSpaceChar(c) && c != '.') {
            if (c == 'e' || c == 'E')
                return res * Math.pow(10, readInt());
            if (c < '0' || c > '9')
                throw new InputMismatchException();
            res *= 10;
            res += c - '0';
            c = read();
        }
        if (c == '.') {
            c = read();
            double m = 1;
            while (!isSpaceChar(c)) {
                if (c == 'e' || c == 'E')
                    return res * Math.pow(10, readInt());
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                m /= 10;
                res += (c - '0') * m;
                c = read();
            }
        }
        return res * sgn;
    }
    public long readLong() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        int sgn = 1;
        if (c == '-') {
            sgn = -1;
            c = read();
        }
        long res = 0;
        do {
            if (c < '0' || c > '9')
                throw new InputMismatchException();
            res *= 10;
            res += c - '0';
            c = read();
        } while (!isSpaceChar(c));
        return res * sgn;
    }
    public boolean isSpaceChar(int c)
    {
        if (filter != null)
            return filter.isSpaceChar(c);
        return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
    }
 
    public String next()
    {
        return readString();
    }
 
    public interface SpaceCharFilter
    {
        public boolean isSpaceChar(int ch);
    }
    public boolean isEndOfLine(int c) {
        return c == '\n' || c == '\r' || c == -1;
    }
}
class Gnode{
 int value;
 List<Gnode> neighbours;
 Gnode(int x)
{value=x;
 neighbours =new ArrayList<>();
}

}
class Node{
    int value;
    Node left;
    Node right;
    Node(int qw){
        this.value = qw;
        this.left = null;
        this.right = null;
    }
}