The game "Divisibility"

Two players X and Y play the following game:

• They are given a positive integer p and a set A consisting of n different nonnegative integers, A = {a[1], a[2], ..., a[n]}, such that every a[i] is less than p.

• Players play with alternating turns. Each player on his turn deletes a number from the set A.

• If after exactly k turns, the sum of the numbers remaining in A is divisible by p - Player X wins. Otherwise - Player Y wins.

Write a program, which determines who wins if both players play optimally.

Input

On the first line there is the positive integer t - the number of games in this test case.

After that, for each i = 0, 1, ..., t – 1:

• on the (3i + 2)-nd line are the numbers n, k (1 ≤ k ≤ n ≤ 5000) and p (p ≤ 10^18);

• on the (3i + 3)-rd line is either the symbol X, or the symbol Y, denoting which of the players goes first;

• on the (3i + 4)-th line are the space separated numbers a[1], a[2], ..., a[n] (0 ≤ a[i] < p).

Output

Print one line with t symbols (without separators), one symbol for each game in the test case. The i-th symbol should be X, if X wins in the i-th game, no matter how Y plays; otherwise, this symbol should be Y.

Examples