F. Shareefeh vs Zahreyye
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Shareefeh was feeling bored, so she decided to take a nap during 3aser. Shareefeh started having ahlam il 3aser—her dream was about her playing a game of cards with Zahreyye, Abu Shehab's ex-wife.

Shareefeh and Zahreyye were the best card players around, and they decided to face each other after an argument about who loves Abu Shehab more.

They reached the point where they could choose any card from the deck, no matter its position.

To make the game more interesting, Zahreyye introduced new rules. Given a card deck with $$$n$$$ cards where each card has its own value.

Taking turns, when a player draws a card, its value is added to their score, and the opponent's score becomes

$$$opponent's$$$ $$$score$$$ = $$$max(0,$$$ $$$opponent's$$$ $$$score$$$ $$$-$$$ $$$gcd($$$$$$opponent's$$$ $$$score$$$, $$$card$$$ $$$value))$$$

The score of any player will never be less than 0 at any time.

Note that the player can draw the same card any number of times she wants.

The game will consist of $$$k$$$ turns, where in each turn, Shareefeh and Zahreyye take turns drawing a card from the deck (they play alternately — Shareefeh draws a card first, then returns it to the deck, followed by Zahreyye who also draws a card and returns it back to the deck afterward), if both play optimally, who wins?

Input

The first line of input will contain one integer $$$T$$$, which is the number of test cases $$$(1 \leq T \leq 10^4)$$$.

For each test case the first line of input will contain two integers $$$n$$$ $$$(1 \leq n \leq 2 \cdot 10^5)$$$ and $$$k$$$ $$$(1 \leq k \leq 10^{5})$$$ — denotes the number of cards and the number of draws.

The second line contain $$$n$$$ numbers $$$a_i$$$ $$$(1 \leq a_i \leq 10^{5})$$$ — $$$a_i$$$ denotes the value of the $$$i_{th}$$$ card.

It is guaranteed that the sum of $$$n$$$ across all test cases does not exceed $$$2\cdot10^5$$$.

Output

For each test case, print "Shareefeh" if Shareefeh wins, othewise print "Zahreyye"

Example
Input
1
1 7
1
Output
Zahreyye