UOFTAB - The Foxens Treasure


There are $N$ ($1 \leq N \leq 4$) Foxen guarding a certain valuable treasure, which you'd love to get your hands on. The problem is, the Foxen certainly aren't about to allow that - at least, not while they're awake.

Fortunately, through careful observation, you've seen that each Fox has a regular sleep cycle. In particular, the $i$th Fox stays awake for $A_i$ ($1 \leq A_i \leq 23$) hours, then sleeps for $S_i$ ($1 \leq S_i \leq 23$) hours, repeating this pattern indefinitely ($2 \leq A_i+S_i \leq 24$). At the start of your treasure-nabbing attempt, the $i$th Fox is exactly $O_i$ ($0 \leq O_i < A_i+S_i$) hours into its cycle.

There are $T$ ($1 \leq T \leq 20$) scenarios as described above. For each one, you'd like to determine how soon all of the Foxen will be simultaneously asleep, allowing you to grab their treasure, or if this will simply never happen.

Input

First line: 1 integer, $T$

For each scenario:

First line: 1 integer, $N$

Next $N$ lines: 3 integers, $A_i$, $S_i$, and $O_i$, for $i = 1..N$

Output

For each scenario:

1 integer, the minimum number of hours after the start to wait until all of the Foxen are asleep during the same hour. If this will never happen, output the string "Foxen are too powerful" (without quotes) instead.

Example

Input:
2
2
2 1 2
2 2 1
3
1 1 0
1 1 0
1 1 1
Output:
6
Foxen are too powerful
Explanation of Sample:

In scenario 1, the following table illustrates the Foxen's sleeping cycles (with A representing being awake, S representing sleep, and a bold letter representing the start of a sleep cycle):

As can be seen, the first hour during which both Foxen are asleep is 6 hours after the start.

In scenario 2, the first 2 Foxen are always awake and asleep at the same times. However, the third Fox's schedule is exactly flipped, which means that it will never be asleep at the same time as the others.


hide comments
nadstratosfer: 2017-12-25 05:46:26

Spent a little while breaking it down, then just coded what I had figured out - worked on the first try. I love when this happens, and such problems tend to inspire elegant solutions also.

vengatesh15: 2017-03-04 18:16:14

Really Foxens are too powerful...

raghav12345: 2016-01-30 11:10:37

ac in 1 go :)
simply apply same method given in explaining

Rishabh Joshi: 2015-03-19 17:34:47

Think simple! ;) Nice problem.

SWOOSH!!!: 2013-06-14 11:09:54

Can i get some tricky test cases on which my code fails? Submission id 9478521

Last edit: 2013-06-14 11:13:10
Aditya Bahuguna: 2013-05-31 15:45:00

Awesome problem...Thanx Jacob...:) (y)
What a relief!!

Aditya Bahuguna: 2013-05-30 22:53:11

Can u please tell whats wrong in my solution...Submission id 9383381
I m gttng correct answer fr all cases i tried..
Is there some formatting error?

RE: You output "Foxen are too powerful" far too often - it turns out they're not quite that powerful.

Last edit: 2013-05-31 04:02:10

Added by:SourSpinach
Date:2013-05-17
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own problem, used in the 2012 UofT ACM Tryouts