U211994 [数论（图论）III]找规律

~~2022-8-1:修改了数据范围，更改了题目数据。~~ ------------ | 1| 3| 17| 19| ...| | :----------: | :----------: | :----------: | :----------: | :----------: | | 7| 5| 15| 21| ...| | 9| 11| 13| 23| ...| | 31| 29| 27| 25| ...| | ...| ...| ...| ...| ...|

无聊的小明在家玩数字游戏，他在纸上写下了一张表格，并填入了一些数字（如上图），晓东跑过来，他问了一个问题：第 $1$ 行第 $2$ 列的数是多少？小明只用了 $1.0\times10^{-10}s$ 就看出了答案然后用 $\dfrac{1.0}{10^{10}}s$ 回答了这个问题。接下来，小董问了一个问题： 第 $21474$ 行第 $83647$ 列的数是多少？小明居然一下子看不出答案！没办法，他向你求助，不过他不希望等太长时间，并且他也不想再一次被为难，所以他想知道他想知道的所有的数。你只有 $\dfrac{111}{200}s$ 的时间来解决这个问题！你愿意接受这个任务吗？ ------------ Bored Xiao Ming is playing a number game at home. He writes a form on the paper and fills in some numbers (as shown in the figure above). Xiao Dong runs over and asks a question: what is the number in line $1 $ and column $2 $? Xiao Ming only used $1.0 \times10 ^ {- 10} s $ to see the answer, and then answered the question with $\dfrac {1.0} {10 ^ {10}} s $. Next, Xiao Dong asked a question: what is the number of $21474 $ row and $83647 $ column? Xiao Ming can't see the answer at once! No way, he asked you for help, but he didn't want to wait too long, and he didn't want to be embarrassed again, so he wanted to know all the numbers he wanted to know. You only have $\dfrac {111}{200} s $ time to solve this problem! Are you willing to accept the task?

输入有 $1+T=T+1$ 行。 第 $1$ 行，$T$。 第 $2\sim T+1$ 行，每行有且只有两个数 $i$ 和 $j$。 ------------ The input has $1 + T = t + 1 $ lines. Line $1 $, $t $. Line $2 \sim T + 1 $, with only two numbers $i $ and $j $ in each line.

输出有 $T$ 行。 第 $1\sim T$ 行，每行一个数 $f_{i,j}$。 ------------ The output has $t $ lines. Line $1 \sim T $, one number per line $f_ {i,j}$。

~~对于 $5\%$ 的数据，$1\leqslant T\leqslant10^2,1\leqslant i,j\leqslant10^2$； 对于 $20\%$ 的数据，$1\leqslant T\leqslant10^5,1\leqslant i,j\leqslant10^5$； 对于 $35\%$ 的数据，$1\leqslant T\leqslant10^6,1\leqslant i,j\leqslant10^6$，时间限制 $555ms$； 对于 $75\%$ 的数据，$1\leqslant T\leqslant10^7,1\leqslant i,j\leqslant10^{10}$； 对于 $100\%$ 的数据，$1\leqslant T\leqslant10^8,1\leqslant i,j\leqslant10^{18}$，时间限制 $1.5s$； **请注意常数因子带来的程序效率上的影响。**~~ ------------ ~~For data of $5\%$, $1\leqslant t\leqslant10^2,1\leqslant I, j\leqslant10^2$; For data of $20\%$, $1\leqslant t\leqslant10^5,1\leqslant I, j\leqslant10^5$; For data of $35\%$, $1\leqslant t\leqslant10^6,1\leqslant I, j\leqslant10^6$, time limit $555ms$; For data of $75\%$, $1\leqslant t\leqslant10^7,1\leqslant I, j\leqslant10^{10}$; For data of $100\%$, $1\leqslant t\leqslant10^8,1\leqslant I, j\leqslant10^{18}$, time limit $1.5s$; **Please pay attention to the effect of constant factor on program efficiency.**~~