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
/*22 25 1 11
        22 31 19 11
        47 2 1 3
        32 34 11 12
        32 2 2 9
        7 39 14 1
        29 6 2 25
        18 16 4 17
        43 49 1 23
        5 18 15 5
        7 18 10 2
        26 5 1 12
        22 45 21 17
        17 24 3 7
        35 34 19 5
        21 45 36 18
        25 31 7 3
        46 22 7 41
        7 16 16 2
        18 33 12 18
        34 10 4 8
        4 12 9 4
        43 21 17 8
        20 47 31 5
        17 17 13 13
        36 4 3 4
        6 31 19 5
        3 2 2 2
        25 35 19 14
        27 49 17 5
        50 20 18 39
        42 30 7 17
        8 31 18 2
        23 29 2 15
        20 5 3 8
        7 35 3 4
        30 11 5 8
        34 4 1 34
        15 36 30 2
        42 26 22 1
        12 7 7 7
        11 35 13 11
        30 14 14 22*/
//import com.sun.source.tree.Tree;

import javax.print.DocFlavor;
import java.util.*;
import java.lang.*;
import java.util.*;
import java.util.stream.*;
import java.io.*;
import java.util.stream.Collectors;

/* Name of the class has to be "Main" only if the class is public. */
public class common {
    public static void main(String[] args) throws java.lang.Exception {
        FastReader sc = new FastReader();
        BufferedWriter w=new BufferedWriter(new PrintWriter(System.out));
        //System.out.println("enter the number of test cases");
        int t=sc.nextInt();
        for(int i=0;i<t;i++) {
            int n= sc.nextInt();
            int m=sc.nextInt();
            int a=sc.nextInt();
            int b=sc.nextInt();
            int ans[][]=new int [n][m];
            if(n*a==m*b)
            {
                w.write("YES\n");
                int []count=new int [m];
                for(int x=0;x<n;x++ )
                {
                    //System.out.println("X: "+x);
                    Map cols=new TreeMap();
                    for(int y=0;y<m;y++)
                    {
                        if(count[y]<b)
                        {
                            cols.put(y,count[y]);
                        }
                    }
                    cols=sortByValue(cols);
                    //System.out.println(cols.toString());
                    Object keys[]=cols.keySet().toArray();
                    for(int ii=0;ii<a;ii++)
                    {
                        int j=(int)keys[ii];
                        count[j]++;
                        ans[x][j]=1;
                    }

                }
                for(int x=0;x<n;x++)
                {
                    for(int y=0;y<m;y++)
                    {
                        w.write(ans[x][y]+"");
                    }
                    w.write("\n");
                }

            }
            else
            {
                w.write("NO\n");
            }
        }

        w.close();
    }
    public static Map<String, Integer> sortByValue(final Map<String, Integer> wordCounts) {

        return wordCounts.entrySet()

                .stream()

                .sorted(Map.Entry.<String, Integer>comparingByValue())

                .collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue, (e1, e2) -> e1, LinkedHashMap::new));

    }
}
class FastReader
{
    BufferedReader br;
    StringTokenizer st;

    public FastReader() throws IOException
    {
        br = new BufferedReader(new
                InputStreamReader(System.in));

    }

    String next() throws NumberFormatException,IOException,NullPointerException
    {
        while (st == null || !st.hasMoreElements())
        {
            st = new StringTokenizer(br.readLine());
        }
        return st.nextToken();
    }

    int nextInt()throws NumberFormatException,IOException,NullPointerException
    {
        return Integer.parseInt(next());
    }

    long nextLong()throws NumberFormatException,IOException,NullPointerException
    {
        return Long.parseLong(next());
    }

    double nextDouble()throws NumberFormatException,IOException,NullPointerException
    {
        return Double.parseDouble(next());
    }

    String nextLine()
    {
        String str = "";
        try
        {
            str = br.readLine();
        }
        catch (IOException e)
        {
            e.printStackTrace();
        }
        return str;
    }
}
