## 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 wi, outputs HAPPY if it is possible to make a friend list for each dog i of length wi, 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.

### Input

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 = 0xi+1 = (a*xi + b) % m`

The sequence of wishes is wi = xi + c.

### Output

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

### Example

```Input:
3
3 2 1 0 2
5 1 1 0 5
6 1 1 1 3

Output: