Free Lunch

Time Limit: 3 Seconds    Memory Limit: 65536 KB

Bahman is participating in a very popular cooking game show. The prize of the winner is a free lunch at the ACM ICPC.
The goal of the game is to make the best cake out of some raw cooking ingredients. The judges are very picky, so Bahman needs to follow the instructions of making the cake better very precise. The host provided the participants all the N raw ingredients they can use. All these N ingredients are in separated containers, ordered C1 to Cn. The only rule of the game is that you can not take ingredients freely. This rule is as follows.

  1. You choose any container Ci and any positive integer d.
  2. You take exactly d grams of ingredient from container Ci.
  3. You choose K > 0 containers from the set {Cj | j < i}, and get some ingredients (in grams, integer) from them, in a way that the total weight of those ingredients from these K containers becomes equal to d.

You can repeat this procedure as many times as needed, but you can not throw away any grams of ingredients you take.
Bahman has several cooking recipes, but he does not know if it is possible to take the required ingredients by the rule of the game or not. Assume that the capacity of each container is infinite.
Write a program that given the required ingredients for a recipe, determines the possibility of taking that ingredients by the rule.

Input

The input contains several test cases.
In the first line of input comes T (0 < T < 64), the number of test cases.
For each case, the first line contains an integer N(1 ≤ N ≤ 106) indicating the number of containers. Then followed by N lines, the ith line contains an integer D i(0 ≤ Di ≤ 109) which shows we need D i grams of the ithcontainer’s ingredient.

Caution! Use fast IO functions as the input file is very big.

Output

For each test case, output a line with the string “YAAAYYYY” if Bahman can win the game and “NOOOO” otherwise.

Sample Input

2
3
2
4
2
3
1
2
2

Sample Output

YAAAYYYY
NOOOO
Submit

Source: 12th Iran Nationwide Internet Contest - Final