Juspay Hiring Process Round-2

Problem

Two players, X and Y, are playing with batteries.

There are n batteries, and the i-th battery starts with ai units of charge.

Player X always moves first. On each turn, a player selects a non-empty battery and removes exactly one unit of charge from it. However, the battery used in the previous turn cannot be chosen again in the current turn.

The player who cannot make a move on their turn loses.

Given the setup for t games, determine who wins if both play optimally.

Input

First line: an integer t ( 1 ≤ t ≤ 100 ) - number of games.

For each game: First line: n ( 1 ≤ n ≤ 100 ) - number of batteries. Second line: a1, a2, ..., an ( 1 ≤ ai ≤ 100 ).

Output

For each game, print "X" if player X wins, otherwise "Y"