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 sys
from collections import defaultdict as dd
def eprint(*args):
    print(*args, file=sys.stderr)
zz=1
from math import *
import copy
#sys.setrecursionlimit(10**6)
if zz:
	input=sys.stdin.readline
else:	
	sys.stdin=open('input.txt', 'r')
	sys.stdout=open('all.txt','w')
def li():
	return [int(x) for x in input().split()]
def fi():
	return int(input())
def si():
	return list(input().rstrip())	
def mi():
	return 	map(int,input().split())	

def bo(i):
	return ord(i)-ord('a')

import copy
t=fi()
while t>0:
	t-=1
	n,m,a,b=mi()	
	d=[['0' for i in range(m)] for j in range(n)]
	i=0
	j=0
	flag=0
	for k in range(b*m):
		if d[i][j]=='1':
			#print(i,j,"LOL")
			pp=i-1
			while i!=pp-1 and d[i][j]=='1':
				i+=1
				i%=n
				if d[i][j]=='0':
					d[i][j]='1'
					f=1
					break
			i=(i+1)%n
			j=(j+1)%m		
			if f==0:
				flag=1
				break
		else:
			d[i][j]='1'
			i=(i+1)%n
			j=(j+1)%m	
		#print(i,j)		
		#for ppp in d:		
		#	print(*ppp)

	if flag:
		print("NO")
		continue	
	for i in range(n):
		v=0
		for j in range(m):
			if d[i][j]=='1':
				v+=1
		if v!=a:
			flag=1
			break		
	if flag:
		print("NO")
		continue
	print("YES")
	for i in d	:
		print("".join(i))	