It’s Kirill’s birthday party and his friends are already a bit tipsy. This is mainly due to Kirill’s new drinking game that is so much more entertaining and hipster than the classic beer pong that all the mainstream people play.

The game works as follows: Kirill gives each of his \(n\) friends a card with an integral number \(a_i\) and then asks them to choose a seat around one of the \(\lfloor n/3 \rfloor\) available circular tables. As any of Kirills friends would like to be able to communicate with at least two other people, a table either remains empty or has at least three people sitting around it. As soon as everybody is seated, Kirill walks around each table and checks if the sum of the cards of two people sitting directly next to each other is a prime number. If this holds for all neighbors at every (non-empty) table, then the so-called "Kirillian condition" is fulfilled. In this case Kirill’s friends win the round and Kirill has to take a shot of the famous vodka Kirillionostrarowitschkanow that he imported from his hometown in Russia. If - on the other hand - the Kirillian condition does not hold, then all of Kirill’s friend have to drink a shot Kirillionostrarowitschkanow.

While Kirill says "Cheers!" every time he has to drink, his friends keep screaming "Na Sdorowje!" from the top of their lungs in case they cannot fulfill the Kirillian condition. For some stupid reason they think that "Na Sdorowje!" is the Russian version of “Cheers!” even though Kirill has already told them a million times that there does not exist an equivalent phrase for "Cheers!" in the Russian language. But what can you do if all of your friends are drunk and won’t listen to the native speaker!?

Since Kirill’s friends are exceptionally gifted in mathematics they always manage to find a seating arrangement that fulfills the Kirillian condition if the cards allow for one.

Given the set of cards that Kirill hands his friends, can you figure out who is gonna be the winner of the game?


The first line of the input contains an integer \(1 \leq t \leq 100\). \(t\) test cases follow, each of them separated by a blank line.

Each test case starts with one integers \(3 \leq n \leq 500\), where \(n\) is the number of guests at Kirill's birthday party. The next line contains \(n\) space separated integers \(\geq 2\) and \(\leq 1000\) which are the numbers on the cards that Kirill hands his guests.


For each test case, output one line containing either Cheers! (if Kirill's guests find a seating arrangement that fulfills the Kirillian condition) or Na Sdorowje! (if they don't).

Sample Input

3 4 8 9

2 2 2 2 2

Sample Output

Na Sdorowje!

This problem is based on a problem first published at the Technische Universität München and is licensed under a Creative Commons Attribution Share-Alike license (cc by-sa).

Upload Solution

Please log in to submit your solution.


Difficulty (1 vote)
Average test runtime 13.98
Points (changes over time) 10
Tried by 2 users
Solved by 2 users

Global ranking

# Name Runtime Points worth
1 Mac 13.94 10
2 Dark 14.01 10