F. Funky Finding
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Everyone knows the standard ordering of the positive integers:

$$$$$$1, 2, 3, 4, 5, 6, 7, 8, 9, 10, \ldots$$$$$$

Using the usual ordering, it's easy to figure out how far apart any given integers $$$x$$$ and $$$y$$$ are. We can just do subtractions like $$$6-4=2$$$ ($$$6$$$ appears two positions ahead of $$$4$$$) or $$$8-12=-4$$$ ($$$8$$$ appears four positions behind $$$12$$$).

In this problem, we consider a different ordering, the Sharkovskii ordering:

$$$3, 5, 7, 9, \ldots, 6, 10, 14, 18, \ldots, 12, 20, 28, 36, \ldots, 24, 40, 56, 72, \ldots, \ldots, 32, 16, 8, 4, 2, 1$$$

First, we list out the odd numbers greater than $$$1$$$ in increasing order. Then we list out $$$2$$$ times these same odds in increasing order. Then we list out $$$4$$$ times these odds in increasing order. And so on for all the powers of $$$2$$$. Finally, at the very end, we list all the powers of $$$2$$$ in decreasing order. Notice that every positive integer appears exactly once in this ordering.

It just got a bit harder to figure out how far apart two numbers are. $$$2$$$ now appears three positions in front of $$$16$$$, $$$20$$$ appears one position behind $$$28$$$, and for some pairs of integers, the answer might be infinite  — for example, $$$6$$$ appears infinitely many positions in front of $$$3$$$!

But surely a little bit of infinity never scared you. You're given integers $$$x$$$ and $$$y$$$, and you need to find how far ahead of $$$x$$$ $$$y$$$ appears in the Sharkovskii ordering.

Input

Input consists of multiple tests. The first line contains $$$t$$$, the number of tests ($$$1 \le t \le 10^4$$$).

The only line of each test contains two integers $$$x$$$ and $$$y$$$ ($$$1 \le x, y \le 10^9$$$).

Output

For each test, output the difference between the positions of $$$y$$$ and $$$x$$$ in the Sharkovskii ordering. If $$$x$$$ appears before $$$y$$$, this number should be positive, and it should be negative otherwise. Note that if $$$x=y$$$, you should output 0.

If there are an infinite number of integers between $$$x$$$ and $$$y$$$, output either inf or -inf. See the sample input for more details.

Example
Input
5
7 7
3 5
1 3
4 128
93 92
Output
0
1
-inf
-5
inf
Note

In the first test, we output 0 since $$$7=7$$$.

In the second test, we can see that $$$3$$$ appears one spot before $$$5$$$ in the above ordering.

In the third test, note that $$$1$$$ comes at the very end of the order, and $$$3$$$ appears at the very beginning. So $$$1$$$ appears after $$$3$$$, and there are infinitely many elements between them.

In the fourth test, note that the powers of $$$2$$$ are ordered backwards by magnitude, so $$$4$$$ appears after $$$128$$$ (specifically, 5 elements after $$$128$$$).

In the fifth test, we can show that $$$93$$$ appears before $$$92$$$, and there are infinitely many elements between them.

This following is for those curious about the context behind the Sharkovskii ordering. You don't need to read it to solve the problem.

  • Let $$$f : \mathbb{I} \rightarrow \mathbb{I}$$$ be a continuous function over some interval of real numbers.
  • A cycle of length $$$n$$$ over $$$f$$$, is a sequence $$$b_1, b_2, \ldots, b_n$$$ of distinct real numbers such that $$$b_{i+1}=f(b_i)$$$ for all $$$1 \le i \lt n$$$, and $$$b_1 = f(b_n)$$$.
  • A theorem by Oleksandr Sharkovskii (1964) proves that if $$$f$$$ has a cycle of length $$$n$$$, it must also have a cycle of length $$$m$$$ for any $$$m$$$ which appears after $$$n$$$ in the Sharkovskii ordering. So, for example, if $$$f$$$ has a cycle of length $$$3$$$, it must also have cycles of any positive integer length!