You are given four positive integers n, m, a, b (1 ≤ b ≤ n ≤ 50; 1 ≤ a ≤ m ≤ 50). Find any such rectangular matrix of size n × m that satisfies all of the following conditions:

  * each row of the matrix contains exactly a ones; 
  * each column of the matrix contains exactly b ones; 
  * all other elements are zeros. 



If the desired matrix does not exist, indicate this.

For example, for n=3, m=6, a=2, b=1, there exists a matrix satisfying the conditions above:

$$$ \begin{vmatrix} 0 & 1 & 0 & 0 & 0 & 1 \\\ 1 & 0 & 0 & 1 & 0 & 0 \\\ 0 & 0 & 1 & 0 & 1 & 0 \end{vmatrix} $$$

Input

The first line contains an integer t (1 ≤ t ≤ 1000) — the number of test cases. Then t test cases follow.

Each test case is described by four positive integers n, m, a, b (1 ≤ b ≤ n ≤ 50; 1 ≤ a ≤ m ≤ 50), where n and m are the sizes of the matrix, and a and b are the number of ones for rows and columns, respectively.

Output

For each test case print:

  * "YES" (without quotes) and the required matrix (if there are several answers, print any) if it exists, or 
  * "NO" (without quotes) if it does not exist. 



To print the matrix n × m, print n rows, each of which consists of m numbers 0 or 1 describing a row of the matrix. Numbers must be printed without spaces.

Example

Input


5
3 6 2 1
2 2 2 1
2 2 2 2
4 4 2 2
2 1 1 2


Output


YES
010001
100100
001010
NO
YES
11
11
YES
1100
1100
0011
0011
YES
1
1
import java.io.*;
    import java.util.*;
    import java.math.*;
    import java.lang.*;

    import static java.lang.Math.*;

    public class Main implements Runnable
    {
        static class InputReader
        {
            private InputStream stream;
            private byte[] buf = new byte[1024];
            private int curChar;
            private int numChars;
            private SpaceCharFilter filter;
            private BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

            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 String nextLine()
            {
                String str = "";
                try
                {
                    str = br.readLine();
                }
                catch (IOException e)
                {
                    e.printStackTrace();
                }
                return str;
            }
            public int nextInt()
            {
                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 long nextLong()
            {
                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 double nextDouble()
            {
                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, nextInt());
                    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, nextInt());
                        if (c < '0' || c > '9')
                            throw new InputMismatchException();
                        m /= 10;
                        res += (c - '0') * m;
                        c = read();
                    }
                }
                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 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 static void main(String args[]) throws Exception
        {
            new Thread(null, new Main(),"Main",1<<26).start();
        }
        //User-defined functions goes here...
        class pair{
            int x, y;
            pair(int x, int y){
                this.x = x;
                this.y = y;
            }
        }

        class sort_res implements Comparator<pair>{
            public int compare(pair a, pair b){
                if(a.x == b.x)
                    return a.y-b.y;
                return a.x - b.x;
            }
        }

        void swap(int[] a, int pos1, int pos2){
            int temp = a[pos1];
            a[pos1] = a[pos2];
            a[pos2] = temp;
        }

        ArrayList<pair>[] graph;
        int cnt[], ww[];

        void dfs(int node, int p){
            if(graph[node].size()==1 && p != -1)
                cnt[p]=1;
            
            for (pair temp: graph[node]) {
                if(temp.y == p)
                    continue;

                dfs(temp.x, temp.y);

                if(p!=-1)   
                    cnt[p] += cnt[temp.y];
            }
        }

        long getdiff(int i){
            return (cnt[i] * 1l * ww[i] - cnt[i] * 1l * (ww[i]/2));
        }

        class TreeComparator implements Comparator<treepair>{
            public int compare(treepair a, treepair b){
                if(b.x - a.x < 0)
                    return 1;
                else if(b.x - a.x > 0)
                    return -1;
                else
                    return (int)(b.y-a.y);
            }
        }

        class treepair{
            long x;
            int y;

            treepair(long x, int y){
                this.x = x;
                this.y = y;
            }
        }

    
        ArrayList<Integer>[] rg;
        TreeSet<Integer> val;
        int[][] dp;


        int calc(int l, int r){
            if(dp[l][r] != -1)
                return dp[l][r];

            dp[l][r] = 0;

            if(l > r)
                return dp[l][r];

            int flag = 0;
            for (int rr : rg[l]) {
                if(rr == r){
                    flag = 1;
                    break;
                }
            }

            dp[l][r] = Math.max(dp[l][r], flag + (l + 1 > r? 0 : calc(l+1, r)));

            for (int nr : rg[l] ) {
                if(nr >= r)
                    continue;
                dp[l][r] = Math.max(dp[l][r], flag + calc(l, nr) + (nr + 1 > r ? 0 : calc(nr + 1, r)));
            }
            return dp[l][r];
        }

        class freq_comp implements Comparator<Integer>{
            public int compare(Integer a, Integer b){
                return colsc[(int)b] - colsc[(int)a];
            }
        }
        int colsc[];

        public void run()
        {
            InputReader sc= new InputReader(System.in);
            PrintWriter w= new PrintWriter(System.out);

            //Your code goes here...
            int test = sc.nextInt();
            for (int q0=0; q0<test; q0++) {
                int n = sc.nextInt();
                int m = sc.nextInt();
                int a = sc.nextInt();
                int b = sc.nextInt();

                int grid[][] = new int[n][m];
                for (int i=0; i<n; i++) {
                    Arrays.fill(grid[i], 0);
                }
                colsc = new int[m];
                Arrays.fill(colsc, b);

                PriorityQueue<Integer> pq = new PriorityQueue<>(new freq_comp());
                for (int i=0; i<m; i++) {
                    pq.add(i);
                }

                boolean flag = true;
                for (int i=0; i<n; i++) {
                    int tempr = a;
                    for (int j=0; j<m; j++) {
                        
                    }
                    while(tempr > 0){
                        boolean useful = false;
                        ArrayList<Integer> useless = new ArrayList<>();
                        int j = -1;

                        while(pq.size() > 0){
                            int k = pq.poll();
                            if(grid[i][k] == 1){
                                useless.add(k);
                            }
                            else{
                                j = k;
                                break;
                            }
                        }

                        if(j == -1)
                            break;

                        for (int pp : useless) {
                            pq.add(pp);
                        }

                        if(tempr > 0 && colsc[j] > 0){
                            grid[i][j] = 1;
                            tempr --;
                            colsc[j] --;
                            useful = true;
                        }
                        pq.add(j);
                        if (!useful) {
                            break;
                        }
                    }
                    

                    if(tempr > 0){
                        flag = false;
                        break;
                    }
                }

                boolean fflag = true;
                for (int i=0; i<m; i++) {
                    if(colsc[i] > 0){
                        fflag = false;
                        break;
                    }
                }

                if(flag && fflag){
                    w.println("YES");
                    for (int i=0; i<n; i++) {
                        for (int j=0; j<m; j++) {
                            w.print(grid[i][j]);
                        }
                        w.println();
                    }
                }
                else
                    w.println("NO");


            }

            w.close();
        }
    }
