UF2015F - Rectangular Spirals

Vatsal (a member of the UF Programming Team) is notorious for wandering around campus without any sense of direction. After every walk Vatsal begins to wonder if he ever crossed over his path. Can you help him out?

Vatsal begins each of his walks at the center of campus facing east. During the ith stage in his walk he moves a distance of di and then turns 90 degrees counterclockwise. If at any stage Vatsal ever walks over his path it is said to be self intersecting.

Input

The input will begin with a line containing a single positive integer t representing the number of paths you must process. Following will be t lines each containing a sequence of positive integers that are space delimited which represent a single instance of wandering Vatsal has done. No sequence will have more than 1,000 stages and no di will be greater than 100,000.

Output

For each walk, print "Yes" if the walk is self intersecting and "No" otherwise. The output for each walk should be on its own line.

Example

Input:
2
5 3 5 2 4
3 3 4 4 5 2 1 Output: No
Yes

Added by:Cormac
Date:2015-02-19
Time limit:0.5s-1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 JS-MONKEY
Resource:UF High School Programming Contest 2015

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.