Ildar Yalalov is a famous eagle with the head of an uzbek guy. He is a very famous competitive programmer in Russia.

But what people don't know that his friend Sergey was feeding him for 3 months so that his wings grow. Few months ago Yalalov was in the top 20 in some VK cup round. In the next round he missed solving 1 problem because he forgot how to use setprecision function properly.

Sergey was very angry, because he spent all these months training Yalalov and growing his wings but for nothing so he decided to quit that and moved on to some other talented guys.

Ildar decided to challenge Sergey to some game to prove that Sergey is no more than a beginner problem-solver.

There are N piles of stones, the i^th pile contains A_i stones. Ildar and Sergey are playing a game, they take turns and Ildar starts the first move.

In each turn, the current player has two options:

1) Remove one stone from any pile.

2) Remove one stone from every pile if every pile has at least 1 stone.

The player who can't make a move loses. Can you determine the winner if both players play optimally?

Print "Yalalov" if Ildar Yalalov wins, and "Shin" otherwise.

Input

The first line contains a single integer T, the number of test cases.

Each test case starts with a line containing a single integer N, the number of piles. (1 ≤ N ≤ 100)

The following line contains N space-separated integers A_i, the number of stones in each pile. (1 ≤ A_i ≤ 10⁶)

Output

For each test case, print "Yalalov" if Ildar Yalalov wins the game, and "Shin" otherwise.

 

不难猜出，胜负与石子堆数n、总石子数sum以及石子最少的堆中石子数min的奇偶性有关。

一、n为奇数，sum为奇数：

　　此时无论进行哪种操作，都只能带走奇数个石子。而总石子数为奇数，故先行者胜。

二、n为奇数，sum为偶数：

　　此时两种操作带走的石子数依旧为奇数，但总石子数为偶数，故后行者胜。

三、n为偶数，sum为偶数：

　　假设先行者先取一个石子，则后行者也可以取一个石子，回到一开始的局面。这种状况持续下去先行者必败。但如果先行者拿走n个石子，就可以将上述状态转给对方，对方要想不败，也得拿走n个石子。这时不难发现胜负取决于min的奇偶性。min为奇则先行者胜，反之后行者胜。

四、n为偶数，sum为奇数：

　　先行者先取一个石子，转化成局面三。之前说过局面三的胜负取决于min的奇偶性，那先行者让min为偶数就可以了。具体做法是如果min是奇数，就从min这一堆中取，否则找别的堆。又因为所有堆的石子数不会一样小（sum为奇数），所以此时先行者必胜。

#include<bits/stdc++.h>
using namespace std;
int a[150];
int main()
{
    int t;
    cin>>t;
    while(t--){
        int n;
        scanf("%d",&n);
        int sum=0,min0=10000000;
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
            sum+=a[i];
            min0=min(min0,a[i]);
        }
        if(n%2==1){
            if(sum%2==1) printf("Yalalov\n");
            else printf("Shin\n");
        }
        else{
            if(sum%2==1) printf("Yalalov\n");
            else{
                if(min0%2==1) printf("Yalalov\n");
                else printf("Shin\n");
            }
        }
    }
    return 0;
}