Happy Number Queries

You are given an integer Q representing the number of queries, followed by Q positive integers. A number is called a happy number if, when you repeatedly replace the number by the sum of the squares of its digits, you eventually reach 1. Otherwise, the number is sad.

In mathematical terms, let \( S(n) = \sum_{d \in digits(n)} d^2 \). Starting from any positive integer \( n \), compute \( n, S(n), S(S(n)), \dots \). If this sequence eventually reaches 1, then \( n \) is a happy number; if the sequence enters a cycle that does not include 1, then \( n \) is a sad number.

For instance, \( 19 \) is a happy number because:

\(19 \to 1^2 + 9^2 = 82 \to 8^2 + 2^2 = 68 \to 6^2 + 8^2 = 100 \to 1^2 + 0^2 + 0^2 = 1\).

inputFormat

The input consists of two lines. The first line contains a single integer \( Q \) (\(1 \le Q \le 10^5\)) representing the number of queries. The second line contains \( Q \) space-separated positive integers, each no greater than \(10^9\).

outputFormat

For each query, print a single line with the word Happy if the number is a happy number, or Sad if it is not.

4
19 2 7 20

Happy
Sad
Happy
Sad