Sử dụng tính chất của dãy số Fibonacci $(F_0=0,F_1=1,F_i=F_{i-1}+F_{i-2}\mathrm{\forall }i\ge 2)$, các hình vuông cạnh $F_1,F_2,...,F_7$ được dựng trên mặt phẳng tọa độ như sau:

Tương tự các hình vuông cạnh $F_i$ cũng được dựng trên mặt phẳng tọa độ theo quy tắc trên. Với cách dựng này thì mặt phẳng tọa độ được phủ kín bởi các hình vuông Fibonacci. Đặt gốc tọa độ là đỉnh dưới bên trái của hình vuông $F_1$, với một điểm cho trước hãy tìm số thứ tự của hình vuông Fibonacci chứa điểm đó ở miền trong.

Chú ý: Điểm nằm trên cạnh của đa giác không được tính là nằm trong đa giác.

Đầu vào

Dòng đầu tiên chứa số nguyên $t$, số lượng test con $(1\le t\le 2\ast {10}^5)$.

$t$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $x$ và $y$ $(0\le x,y\le 5\times {10}^{17})$ mô tả tọa độ của điểm.

Đầu ra

$t$ dòng, dòng thứ $i$ chứa một số nguyên $k_i$ với $F_{k_i}$ là cỡ của hình vuông chứa điểm thứ $i$. Nếu điểm thứ $i$ không nằm trong hình vuông nào thì xuất ra $-1$.

Ví dụ

Đầu vào:

7
2 1
2 2
2 3
9 0
9 1
4 6
4 5

Đầu ra:

3
-1
4
-1
7
6
-1