SP18458 VFRIEND2 - Very Friends 2

You are creating a new soical network for dogs. Wow. The dogs don't have many possibilities for interacting with your website, but they can bark how many friends they want. E.g. if a dog wants to have much 8 friends it will bark 8 times, and if it doesn't want any friends, it'll just stay quiet. After spending a good year of your life collecting these barks, you are finally ready to assign a friend list for each dog. The only problem is: You are not sure whether it is actually possible. Thus before you proceed you would like to write a program, that given a list of **N** wishes **w $ _{i} $** , outputs **HAPPY** if it is possible to make a friend list for each dog **i** of length **w $ _{i} $** , or **SAD** if some dog will have to get more or fewer friends than it wished for. Notice: Being friends is considered a reflexive relation.

The first line will contain a single integer **T** - the number of test cases to process. Because of I/O constraints, the sequence of wishes is not given explicitly. Each of the **T** lines will consist of 5 integers **N**, **a**, **b**, **c**, **m** in the range **\[0, 10^7\]** (except **m** which is in **\[1, 10^7\]**). These integers describe the sequence ``` x0 = 0 xi+1 = (a*xi + b) % m ``` The sequence of wishes is **w $ _{i} $** = **x $ _{i} $** + **c**.

Write the answer - **HAPPY** or **SAD** - for each test case on a separate line.