Superlatives

Interview

Time limit1sMemory limit128 MB

Summary
Given expected rain E and actual rain A, print how many times the word mega precedes drought based on the ratio E/A, or no drought if E <= A.
Level

Easy3 of 10

Topics
Implementation, Math, Simulation
Solved
No attempts yet

Problem

Droughts are usually classified as "abnormally dry", "moderate drought", "severe drought", "extreme drought", and "exceptional drought". The current drought is so "exceptional" across most of California that people have discussed adding one or more steps to the scale. But that would only delay the problem: any system of discrete labels eventually fails to scale. As computer scientists, we know the answer is a naming system to which you can simply keep adding syllables. So how about "mega drought", "mega mega drought", "mega mega mega drought", and so on? It extends arbitrarily. In this problem you write a program that decides how many "mega" prefixes to add.

You are given two numbers: the amount of rain that was expected and the amount of rain that actually fell. Let EE be the expected amount and AA the actual amount.

  • If the expected amount does not exceed the actual amount (E≤AE \le A), there is no drought.
  • If the expected amount is more than the actual amount but by a factor of at most 5 (A<E≤5AA < E \le 5A), it is a drought.
  • If the factor is strictly greater than 5 but at most 25 (5A<E≤25A5A < E \le 25A), it is a mega drought.
  • If the factor is strictly greater than 25 but at most 125 (25A<E≤125A25A < E \le 125A), it is a mega mega drought.
  • In general, each additional factor of 5 adds one more "mega": the answer has mm copies of "mega" exactly when 5m A<E≤5m+1 A5^{m}\,A < E \le 5^{m+1}\,A (with m≥0m \ge 0, where m=0m = 0 is a plain "drought").

Input

The first line contains the number KK of data sets. Then KK data sets follow, one per line.

Each data set contains two integers EE and AA with 0≤E,A≤1,000,0000 \le E, A \le 1{,}000{,}000 and A>0A > 0: the expected and the actual amount of rain, in that order.

Output

For each data set, first output a line "Data Set x:", where xx is the data set's number (starting from 1).

On the following line, output the string describing the drought ("no drought", "drought", "mega drought", "mega mega drought", and so on).

Print a blank line between consecutive data sets.

Examples1

  1. Example 1

    Input
    3
    100 100
    12375 99
    10 2
    
    Expected output
    Data Set 1:
    no drought
    
    Data Set 2:
    mega mega drought
    
    Data Set 3:
    drought