Problem: Andre has very specific tastes. Recently he started falling in love with arrays.

Andre calls an nonempty array b good, if sum of its elements is divisible by the length of this array. For example, array [2, 3, 1] is good, as sum of its elements — 6 — is divisible by 3, but array [1, 1, 2, 3] isn't good, as 7 isn't divisible by 4. 

Andre calls an array a of length n perfect if the following conditions hold: 

  * Every nonempty subarray of this array is good. 
  * For every i (1 ≤ i ≤ n), 1 ≤ a_i ≤ 100. 



Given a positive integer n, output any perfect array of length n. We can show that for the given constraints such an array always exists.

An array c is a subarray of an array d if c can be obtained from d by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.

Input

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

The first and only line of every test case contains a single integer n (1 ≤ n ≤ 100).

Output

For every test, output any perfect array of length n on a separate line. 

Example

Input


3
1
2
4


Output


24
19 33
7 37 79 49

Note

Array [19, 33] is perfect as all 3 its subarrays: [19], [33], [19, 33], have sums divisible by their lengths, and therefore are good.

Solution (in JAVA):

Solution:
import java.util.*;
import java.math.*;
import java.io.*; 
 public class A{

static FastReader scan=new FastReader();
  public static PrintWriter out = new PrintWriter (new BufferedOutputStream(System.out));
  static LinkedList<Integer>edges[];
  static LinkedList<Integer>Same[];
  static LinkedList<Integer>Dif[];
  static LinkedList<Integer>integers[];
static int []dx={1,-1,0,0};
static int []dy={0,0,1,-1};
int dx_8[]={1,1,1,0,0,-1,-1,-1};
int dy_8[]={-1,0,1,-1,1,-1,0,1};
static int n,m;
static boolean prime[];
static long LCM(long a,long b){
    return (Math.abs(a*b))/gcd(a,b);
   }
   static long gcd(long a, long b) {
    if(a!=0&&b!=0)
        while((a%=b)!=0&&(b%=a)!=0);
    return a^b;
}
static int countSetBits(int n) 
    { 
        int count = 0; 
        while (n > 0) { 
            count += n & 1; 
            n >>= 1; 
        } 
        return count; 
    } 
 static void sieve(long n) 
    { 
        
        prime = new boolean[(int)n+1]; 
        for(int i=0;i<n;i++) 
            prime[i] = true; 
          
        for(int p = 2; p*p <=n; p++) 
        { 
           
            if(prime[p] == true) 
            { 
                
                for(int i = p*p; i <= n; i += p) 
                    prime[i] = false; 
            } 
        } 
    }  
    
    static int count;
 
  static boolean canTransmit[][]=new boolean[1000+5][1000+5];

    
    
    static boolean vis[][];
    static int color[]=new int[(int)1e5+5];
   static long cnt[]=new long[2];
static boolean bad=false;
    static void dfs(int v,int col){
        
        color[v]=col;
        for(int i:Dif[v])
        {
            if(~color[i]!=0)
            {
                if(color[i]==color[v])
                    bad=true;
                
            }
            else dfs(i,col^1);
        }
 for(int i:Same[v])
        {
            if(~color[i]!=0)
            {
                if(color[i]==(color[v]^1))
                    bad=true;
                
            }
            else dfs(i,col);
        }
            }
            static char grid[][];
            static char copy[][];
            static int N;
            static boolean e(int x,int y){
                return(x>=0&&x<N&&y>=0&&y<N);
            }
         
           static boolean isprime(long x)
           {
            for(long i=2;i*i<=x;i++)
                if(x%i==0)
                    return false;
                return true;
           }
           static boolean visisted[]=new boolean[(int)1e5+5];
           static int c[]=new int[(int)1e5+5];
           static int contain[]=new int[(int)1e5+5];
           static int ans=0;
           static void dfs_(int v){
            visisted[v]=true;
            if(c[v]>m){
               // out.println(v);
               return;
            }
            int cnt=0;
          for(int i:edges[v])
          {
            //contain[i]=contain[v];
            if(visisted[i])
                continue;
           c[i]=c[v]+1;
           if(contain[i]==0)c[i]=0;
                dfs_(i);
                cnt++;
          }
          if(cnt==0){
        //out.println(v);
            ans++;
        }
           }

public static void main(String[] args)  throws IOException 
{
//java.util.Scanner scan=new java.util.Scanner(new File("revegetate.in"));
 //PrintWriter out = new PrintWriter (new FileWriter("revegetate.out"));
  //  System.out.println(~-1);
    

        //System.out.println(0^1);

//SUCK IT UP AND DO IT ALRIGHT
    //System.out.println(true|true);
 int t=scan.nextInt();
 while(t-->0)
 {
    int n=scan.nextInt();
    for(int i=0;i<n;i++)
        out.print(2+" ");
    out.println();
 }
out.close();
//SEE UP 

}
static long powMod(long base, long exp, long mod) {
       if (base == 0 || base == 1) return base;
       if (exp == 0) return 1;
       if (exp == 1) return base % mod;
       long R = powMod(base, exp/2, mod) % mod;
       R *= R;
       R %= mod;
       if ((exp & 1) == 1) {
           return base * R % mod;
       }
       else return R % mod;
   }
static double dis(double x1,double y1,double x2,double y2)
{
    return Math.sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
static long mod(long x,long y)
    {
        if(x<0)
            x=x+(-x/y+1)*y;
        return x%y;
    }
 public static  long pow(long b, long e) {
            long r = 1;
            while (e > 0) {
                if (e % 2 == 1) r = r * b ;
                b = b * b;
                e >>= 1;
            }
            return r;
        }
private static void sort(long[] arr) {
        List<Long> list = new ArrayList<>();
        for (long object : arr) list.add(object);
        Collections.sort(list);
        for (int i = 0; i < list.size(); ++i) arr[i] = list.get(i);
    }
 public static class FastReader {
        BufferedReader br;
        StringTokenizer root;
        
 
        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        boolean hasNext(){
            String line;
            while(root.hasMoreTokens())
                return true;
            return false;
        }
 
        String next() {
            while (root == null || !root.hasMoreTokens()) {
                try {
                    root = new StringTokenizer(br.readLine());
                } catch (Exception addd) {
                    addd.printStackTrace();
                }
            }
            return root.nextToken();
        }
 
        int nextInt() {
            return Integer.parseInt(next());
        }
 
        double nextDouble() {
            return Double.parseDouble(next());
        }
 
        long nextLong() {
            return Long.parseLong(next());
        }
 
        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (Exception addd) {
                addd.printStackTrace();
            }
            return str;
        }
         public int[] nextIntArray(int arraySize) {
            int array[] = new int[arraySize];
 
            for (int i = 0; i < arraySize; i++) {
                array[i] = nextInt();
            }
 
            return array;
        }
}
 static class Pair implements Comparable<Pair>{
        public int x, y;
        public Pair(int x1, int y1) {
            x=x1;
            y=y1;
        }
        @Override
        public int hashCode() {
            return (int)(x + 31 * y);
        }
        public String toString() {
            return x + " " + y;
        }
        @Override
        public boolean equals(Object o){
            if (o == this) return true;
            if (o.getClass() != getClass()) return false;
            Pair t = (Pair)o;
            return t.x == x && t.y == y;
        }
public int compareTo(Pair o)
{
    return (x-o.y)-(o.x-y);

    }

static class pair{
    int i;
    int j;
pair(int i,int j){
    this.i=i;
    this.j=j;
}}}
 static class tuple{
        int x,y,z;
        tuple(int a,int b,int c){
            x=a;
            y=b;
            z=c;
        }
    }
    static class Edge{
        int d,w;
        Edge(int d,int w)
        {
            this.d=d;
            this.w=w;
        }
    }
}