Balancing Gifts
By Cristhian Bonilha, UTFPR 
Brazil
By Cristhian Bonilha, UTFPR Brazil
Its almost Christmas, and as usual the Santa is getting ready to board his sleigh with all N gifts to be delivered.
The space in which the gifts will be put into in the sleigh can be divided in two sides: side A and side B. To ensure that the sleigh will be balanced, the difference in the sum of gifts on the side A and on the side B can't be greater than 5kg.
You've got the task to help Santa this year. Given the N gifts, you must find out if there's a way to divide them on the sides A and B, ensuring that the sleigh never gets unbalanced.
Notice that the gifts must be alocated one at a time, in the order they are given on the test case, and at every moment the sleigh should be balanced.
There will be T test cases.
Each test case starts with an integer N, indicating the number of gifts to be alocated (1 <= N <= 16*, or 1 <= N <= 10000**).
Following there will be N integers pi, representing the weight of the N gifts (1 <= pi <= 10, for every 1 <= i <= N).
* Will happen at approximately 90% of the test cases.
** Will happen at approximately 10% of the test cases.
For each test case you should print a row, containing the sentence "Feliz Natal!" if its possible to divide the gifts without never losing balance, or "Ho Ho Ho!" otherwise.
| Input Sample | Output Sample |
|
2 |
Feliz Natal! |