2 sec, 256 М
I will tell to all my friends
So difficult to be an insect!
It's not a secret that the ONU students love biology most of all. But few know that it is the student of the Common Entertainment Theory Vasiliy Vulgar brought a new kind of locust - locust Syracuse. This sweet insect lives in flocks and eats anything that comes – a swarm of locusts can eat in a few minutes the young rape crops, hemp, and as he does not shun small reptiles and mammals. The only problem is that insects can’t stand alone – left alone, locusts immediately die of boredom. In addition, numerous observations have allowed the student to bring an interesting pattern: the locust population in the school is changing every day and does not depend on the amount of food or the time of year, but only on the number of insects that are in the school the previous day. If yesterday was the population of N individuals and N is even, now, alas, will be N/2. But if N was odd, we will appreciate a cheerful buzz already 3*N-1 insect today. Now Vasiliy observes a new colony of locusts. Unfortunately, he could not give the exact number of insects in it, and then predict the further development of the population. The only thing he is sure is that the number of insects at least natural number A and no more than a natural number B. Overjoy student Vulgar with news that the colony will live forever, or regret to inform, what is the maximum number of days it can survive. But to tell the truth! Vasiliy feels when somebody lies.
Input. The first line of input contains the number of test cases T (1 ≤ T ≤ 100000). Each of the next T lines contains a single request – a couple of numbers A and B (1 ≤ A ≤ B ≤ 11111).
Output. For each query output -1 if there is a variant in which the colony will live forever. Otherwise, print the maximum number of days that it can reach.
Idea – Igor Eugenevich Mazurok
KBIS Software Developer