题目描述

薯条哥拿到了一个奇怪的二叉树，如下图：

第一层从左往右赋值，第二层从右往左赋值，第三层从左往右赋值…… 以此类推。这个二叉树有无穷多层。

薯条哥有$t$次询问，每次询问输入两个正整数$x,y$，她想知道$x$和$y$在二叉树上的路径长度是多少。你能帮帮她吗？

输入描述

第一行输入一个正整数$q(1\le q\le 10^5)$，代表询问次数。

接下来的$q$行，每行输入两个正整数$x,y(1\le x,y\le 10^9)$，代表一次询问。

输出描述

输出$q$行，每行输出一个整数，代表该次询问的答案。

样例

输入

3
11 4
2 5
7 7

输出

5
3
0