UOJ Logo Universal Online Judge

UOJ

#282. 长度测量鸡

统计

新年到新年到!计算鸡村全村上下家家户户开始贴起了春联。

比起贴春联,计算鸡更喜欢制作春联,除了每家每户制作自己的春联之外,还可以两家一起,一家写上联,一家写下联,凑成一整幅春联。

计算鸡村共有 $n$ 户村民,现在每两户计算鸡都合作制作了一副春联,加上每家每户自己的,一共有 $\frac{n(n+1)}{2}$ 副春联。

计算鸡对春联的长度有这特殊的癖好,他们希望这 $\frac{n(n+1)}{2}$ 副春联长度各不相同,于是计算鸡村长找来一根长度为 $\frac{n(n+1)}{2}$ 的木条,想要把它做成一把尺,使得它能量出不超过 $\frac{n(n+1)}{2}$ 的所有正整数长度。

计算鸡们很懒,他们连划刻度都觉得累,于是他们决定在木条上划出恰好 $n-1$ 个刻度,并使它满足计算鸡村长的条件。

可是有的时候他们想啊想啊,想破鸡蛋都想不出来如何安排刻度,于是他们怀疑根本就不存在安排刻度的方法,想让你帮忙验证。

你只需要对于给定的 $n$,告诉计算鸡们是否存在合法的雕刻刻度的方法。

一个长度 $d$ 能被木条量出当且仅当存在两个不同的刻度之间,刻度与两个端点之间,或木棍两个端点的距离恰好为 $d$。

更加数学的描述:假如你安排的刻度到木棍左端的距离由近至远分别为 $s_1, s_2, \dots, s_{n-1}$,令 $s_0=0,s_n=\frac{n(n+1)}{2}$,则长度 $d$ 能被量出当且仅当存在 $0 \leq i,j \leq n$ 使得 $\lvert s_i-s_j \rvert =d$。

输入格式

多组数据,第一行为数据组数 $T\le10$,以下 $T$ 行为 $T$ 个正整数 $n$。

输出格式

输出共 $T$ 行, 每行为一个整数, 表示能否给出满足要求的刻度。 能则输出 $1$,不能则输出 $-1$。

样例一

input

2
1
100

output

1
-1

限制与约定

对于全部数据满足$1 \leq T \leq 10$,$1 \leq n \leq 2500$。

测试点编号 $n$
1$\le5$
2$\le8$
3$\le20$
4
5$\le100$ 且为质数
6
7$=2017$
8$=2048$
9$\le2500$
10

时间限制:$1\texttt{s}$

空间限制:$256\texttt{MB}$

下载

样例数据下载