Writers

Time limit10sMemory limit1024 MB

Summary

Given text fragments from three Polish novels, output which author wrote each one: Mickiewicz, Prus, or Sienkiewicz.

Level: Easy3 of 10
Topics: String, Hash map
Solved: No attempts yet

Problem

Bajtek found a fragment of text in Polish. He knows only that the fragment comes from one of three books:

"Pan Tadeusz" by Adam Mickiewicz,
"Quo Vadis" by Henryk Sienkiewicz,
"Lalka" by Bolesław Prus.

Write a program that helps him determine which of these books the fragment comes from.

Input

The first line contains the number of test cases $T$ ( $1 \le T \le 1000$ ). Each of the next $T$ lines contains a fragment from one of the three books. A fragment contains no Polish letters, has between 10 and 2000 words, and begins and ends with a complete word or a punctuation mark. The total length of all fragments in the input does not exceed two million characters.

Output

Print $T$ lines. The $i$ -th line contains one word, Mickiewicz, Prus, or Sienkiewicz, which is the author of the $i$ -th fragment.

Hint

Each fragment in the input is the beginning of the corresponding work.

Examples1

Example 1

Input

3
Petroniusz obudzil sie zaledwie kolo...
Litwo! Ojczyzno moja! ty jestes jak...
W poczatkach roku 1878, kiedy swiat...

Expected output

Sienkiewicz
Mickiewicz
Prus