Problem Description

There is a huge directed graph which contains $10^{18}$ nodes numbered from $1$ to $10^{18}$. There is a directed edge from $x$ to $y$ if and only if $x \lt y \leq 500 x$, and the length of the edge is $\ln \left\lfloor \left\lfloor \sqrt\frac{y}{x} \right\rfloor ^\frac{3}{2} \right\rfloor$, where $\ln$ is natural logarithm, and $\lfloor x \rfloor$ denotes the biggest integer that is not bigger than $x$.

You are given two integers $x$ and $y$ ($x \lt y$), and you need to find the **longest** path from $x$ to $y$. If the longest path is $d$, you just need to output $\lfloor e^d \rfloor$, where $e$ is the base of natural logarithm.

Input

The first line of input contains an integer $T\;(1\leq T \leq 200000)$, denoting the number of test cases.

In the next $T$ lines, each line contains two integers $x$ and $y$ ($1\leq x \lt y \leq 10^{18}$).

Output

For each test case, print one integer in one line, denoting $\lfloor e^d \rfloor$.

4
2 8
3 27
4 64
1 12345678987654321

2
5
8
1163817123840