---{"category_name":"easy","problem_code":"GAMEW","problem_name":"Games of Wasseypur","problemComponents":{"constraints":"- $1 \\leq T \\leq 10^4$\n- $1 \\leq N \\leq 10^5$\n- $S$ is a binary string, consisting of $0$ and $1$ only\n- Sum of $N$ over all test cases will not exceed $10^6$\n","constraintsState":true,"subtasks":"- 30 points : $1 \\leq R \\leq 10000$\n- 70 points : $1 \\leq R \\leq 10^9$\n","subtasksState":false,"inputFormat":"- The first line of input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.\n- The first line of each test case contains a single integer $N$ denoting the length of the string.\n- The second line of each test case contains the binary string $S$.","inputFormatState":true,"outputFormat":"For each test case, output a single line containing the string “SAHID” (without quotes) if Sahid Khan will be the winner, and “RAMADHIR” otherwise.\n\nEach character of the output can be printed either in lowercase or uppercase (so if Sahid wins, “SAHID”, “sahid” and “sAHiD” are all acceptable outputs).\n","outputFormatState":true,"sampleTestCases":{"0":{"id":1,"input":"2\n4\n0000\n4\n0011","output":"SAHID\nRAMADHIR","explanation":"**Test case 1:**\nThere is only one block $0000$, which Sahid Khan will erase in the first move. Ramadhir Singh is then left unable to make a move and loses.\n\n\n**Test case 2:**\nThere are two blocks- $00$ and $11$. Sahid has to erase any one of the two, following which Ramadhir will erase the remaining block and make the string empty. Now, Sahid cannot make a move and will lose the game.\n","isDeleted":false}}},"video_editorial_url":"https://youtu.be/ZwqIWQDsjBU","languages_supported":{"0":"CPP14","1":"C","2":"JAVA","3":"PYTH 3.6","4":"CPP17","5":"PYTH","6":"PYP3","7":"CS2","8":"ADA","9":"PYPY","10":"TEXT","11":"PAS fpc","12":"NODEJS","13":"RUBY","14":"PHP","15":"GO","16":"HASK","17":"TCL","18":"PERL","19":"SCALA","20":"LUA","21":"kotlin","22":"BASH","23":"JS","24":"LISP sbcl","25":"rust","26":"PAS gpc","27":"BF","28":"CLOJ","29":"R","30":"D","31":"CAML","32":"FORT","33":"ASM","34":"swift","35":"FS","36":"WSPC","37":"LISP clisp","38":"SQL","39":"SCM guile","40":"PERL6","41":"ERL","42":"CLPS","43":"ICK","44":"NICE","45":"PRLG","46":"ICON","47":"COB","48":"SCM chicken","49":"PIKE","50":"SCM qobi","51":"ST","52":"SQLQ","53":"NEM"},"max_timelimit":0.5,"source_sizelimit":50000,"problem_author":"rag_hav13","problem_tester":"","date_added":"30-09-2021","tags":{"0":"csns2021","1":"observation","2":"rag_hav13","3":"simple"},"problem_difficulty_level":"Unavailable","best_tag":"","editorial_url":"https://discuss.codechef.com/problems/GAMEW","time":{"view_start_date":1635960600,"submit_start_date":1635960600,"visible_start_date":1635960600,"end_date":1735669800},"is_direct_submittable":false,"problemDiscussURL":"https://discuss.codechef.com/search?q=GAMEW","is_proctored":false,"visitedContests":{},"layout":"problem"}---Everything was going well in Wasseypur until Ramadhir Singh came to know that Sahid Khan plans to kill him someday, and takeover his mine. So he decided to take preemptive measures and kill Sahid Khan first. However Sahid Khan also came to know Ramadhir Singh's plan to kill him soon. Wasseypur was all set for bloodshed but the Chef intervened. Instead of violence, he convinced both to play a game called Game of Wasseypur.There is a string $S$ of length $N$ consisting of only $0's$ and $1's$. The Game is played in turns, in each turn a player can erase a $block$ from the current string and the remaining part of the string will concatenate to make the current string for another player.A block in the string is defined as a non-empty substring consisting of the same character such that both the neighbouring character(s) (if exists) are different from the character of the substring. $Eg: S = “0001110110011”$In the above string, there are $6$ blocks which are $000,111,0,11,00,11$The player who will not be able to make a move at the end will lose the game and so will have to leave the Wasseypur. Both Sahid Khan and Ramadhir have taken the help of Wasseypur's elders and will play optimally. Assuming the game will start from the Sahid khan, find out the winner.<aside style='background: #f8f8f8;padding: 10px 15px;'><div>All submissions for this problem are available.</div></aside>