Wolfgang Puck is not doing so well financially and has accepted a position as a lowly chef at a restaurant franchise named after himself. He is not able to live his normal, lavish lifestyle and as a result he has recently developed some odd tendencies. One tendency in particular is that with his recipe books he can only flip a precise number of pages left (backwards) or a number of pages right (forwards).
Wolfgang must make a dish he knows to be on a certain page of his recipe book. If he starts from the first page, is he able to reach this page? If so, what is the least number of page flips he can make to reach this page?
On the first line you are given c (1 ≤ c ≤ 100), the number of occurrences Wolfgang has with his flipping frustration. For each occurrence you are given n l r t (2 ≤ n ≤ 107, 1 ≤ l, r ≤ n-1, 1 ≤ t ≤ n) on a line where n is the number of pages in the book, l is the interval left, r is the interval right, and t is the target page number.
If it is possible to reach page t from page 1, output on a single line the minimum number of page flips. If it is not possible, print "uh-oh!" on a line.
5 10 5 4 1 1000 2 1 42 100 2 4 66 101 60 70 51 100 2 3 98
0 41 uh-oh! uh-oh! 34