Polycarp remembered the 2020-th year, and he is happy with the arrival of the new 2021-th year. To remember such a wonderful moment, Polycarp wants to represent the number n as the sum of a certain number of 2020 and a certain number of 2021.

For example, if: 

  * n=4041, then the number n can be represented as the sum 2020 + 2021; 
  * n=4042, then the number n can be represented as the sum 2021 + 2021; 
  * n=8081, then the number n can be represented as the sum 2020 + 2020 + 2020 + 2021; 
  * n=8079, then the number n cannot be represented as the sum of the numbers 2020 and 2021. 



Help Polycarp to find out whether the number n can be represented as the sum of a certain number of numbers 2020 and a certain number of numbers 2021.

Input

The first line contains one integer t (1 ≤ t ≤ 10^4) — the number of test cases. Then t test cases follow.

Each test case contains one integer n (1 ≤ n ≤ 10^6) — the number that Polycarp wants to represent as the sum of the numbers 2020 and 2021.

Output

For each test case, output on a separate line: 

  * "YES" if the number n is representable as the sum of a certain number of 2020 and a certain number of 2021; 
  * "NO" otherwise. 



You can output "YES" and "NO" in any case (for example, the strings yEs, yes, Yes and YES will be recognized as positive).

Example

Input


5
1
4041
4042
8081
8079


Output


NO
YES
YES
YES
NO
# import sys 
# sys.stdin = open('input.txt', 'r')
# sys.stdout = open('output.txt', 'w')
def isHill(i):
	if i==0 or i==n-1:
		return 0
	if l[i]>l[i-1] and l[i]>l[i+1]:
		return 1
	return 0

def isVal(i):
	if i==0 or i==n-1:
		return 0
	if l[i]<l[i-1] and l[i]<l[i+1]:
		return 1
	return 0

def count(i):
	return isHill(i)+isVal(i)

mod = int(1e9)+7
N = 1000001
l = [0]*N
for i in range (2020, N, 2020):
	for j in range (i, N, 2021):
		if l[j]==1:
			break
		l[j] = 1

for i in range (2021, N, 2021):
	l[i] = 1

def ip(mode):
	if mode==0:
		return int(input())
	if mode==1:
		return list(map(int, input().split()))
	if mode==2:
		return input()
	if mode==3:
		return list(map(str, input().split()))
	if mode==4:
		return map(int, input().split())
	if mode==5:
		return map(str, input().split())

for _ in range(int(input())):
	n = ip(0)
	if l[n]:
		print("YES")
	else:
		print("NO")
	