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.*;

public class solution {
    static FastReader sc;
    static OutputStream outputStream = System.out;
    static PrintWriter out = new PrintWriter(outputStream);


    static class FastReader
    {
        BufferedReader br;
        StringTokenizer st;

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

        public FastReader(String filePath)
        {
            try{
            br = new BufferedReader(new
                    FileReader(filePath));

            }
            catch(FileNotFoundException e)
            {
                out.println(e);
            }

        }

        String next()
        {
            while (st == null || !st.hasMoreElements())
            {
                try
                {
                    st = new StringTokenizer(br.readLine());
                }
                catch (IOException  e)
                {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt()
        {
            return Integer.parseInt(next());
        }

        long nextLong()
        {
            return Long.parseLong(next());
        }

        double nextDouble()
        {
            return Double.parseDouble(next());
        }

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


    public static long minDigit(long n) {
        long minDigit = 9;
        while (n > 0) {
            if ((n % 10) < minDigit) {
                minDigit = n % 10;
            }
            n /= 10;
        }
        return minDigit;
    }

    public static long maxDigit(long n) {
        long maxDigit = 0;
        while (n > 0) {
            if ((n % 10) > maxDigit) {
                maxDigit = n % 10;
            }
            n /= 10;
        }
        return maxDigit;
    }

    public static void solve() throws Exception {
        int n=sc.nextInt(),m=sc.nextInt(),a=sc.nextInt(),b=sc.nextInt();
        int[] rowCount = new int[n];
        int[] colCount = new int[m];
        int[][] arr = new int[n][m];
        Arrays.fill(rowCount,a);
        Arrays.fill(colCount,b);
        boolean isPossible=true;
        int j1=0;
        for(int i=0;i<n;i++)
        {
            for (int j = 0; j < m; j++) {
                j1%=m;
                if (rowCount[i] > 0 && colCount[j1] > 0) {
                    arr[i][j1] = 1;
                    rowCount[i]--;
                    colCount[j1]--;
                    j1++;
                } else {
                    arr[i][j1] = 0;
                }
            }
        }
        for(int i=0;i<n;i++)
        {
            if(rowCount[i]>0)
            {
                isPossible=false;break;
            }
        }
        for(int i=0;i<m;i++)
        {
            if(colCount[i]>0)
            {
                isPossible=false;break;
            }
        }
        if(isPossible)
        {
            out.println("YES");
            for(int i=0;i<n;i++)
            {
                for(int j=0;j<m;j++)
                {
                    out.print(arr[i][j]);
                }
                out.println();
            }
        }
        else
        {
            out.println("NO");
        }
    }

    public static void main(String[] args) throws Exception {
        if (System.getProperty("ONLINE_JUDGE") == null) {
            sc = new FastReader("/Users/jenardn/IdeaProjects/codeforces/input");
        } else {
            sc = new FastReader();
        }
        int t = sc.nextInt();
        while (t-- > 0) {
            solve();
        }
        out.close();
    }

}

class Pair implements Comparable<Pair> {
    int size, first, second;

    Pair(int first, int second) {
        this.size = second - first;
        this.first = first;
        this.second = second;
    }

    public int compareTo(Pair other) {
        if (this.size > other.size)
            return -1;
        else if (this.size < other.size)
            return 1;
        else {
            if (this.first < other.first)
                return -1;
            else if (this.first > other.first)
                return 1;
            return 0;
        }
    }
}