Description

由k个正整数组成的数组a如果是[a1,a2,a3......ak]=[ak......a3,a2,a1]，我们就称这个数组为回文数组。例如[1,2,1]和[5,1,1,5]是回文数组。

如果任何整数n(n>=k)都可以表示为一个长度正好为k的回文数组的元素之和，我们就称这个数k为理想发电数。数组中的每个元素都必须大于0。

例如数字1是一个理想发电数，因为任何自然数n都额可以用数组[n]生成。数字2不是一个理想发电数，因为n=3时，不存在一个长度为2的回文数组，使得数组的和是3。

请判断给定的数字k是否是理想发电数。

Input Format

第一行输入一个整数t，表示有t组测试数据。

接下来t行，每行一个正整数k。

t<=1000,k<=1e4。

Output Format

5
1
2
3
73
1000

YES
NO
YES
YES
NO

Source