J. Graph Changing
time limit per test
3 s
memory limit per test
32 megabytes
input
standard input
output
standard output

There are $$$10^9+1$$$ graphs with $$$n$$$ vertices each. In the $$$0$$$-th graph $$$G_0(V_0,E_0)$$$, there is an edge between vertices $$$i$$$ and $$$i+1$$$ for all $$$1\leq i \lt n$$$.

Denote the length of the shortest path between $$$x$$$ and $$$y$$$ in the graph $$$i$$$ by $$$d_{i}(x,y)$$$. If $$$x$$$ and $$$y$$$ aren't reachable from each other, let $$$d_i(x,y)$$$ be $$$-1$$$. In the graph $$$i$$$ ($$$i\geq 1$$$), there's an edge between $$$x$$$ and $$$y$$$ if and only if $$$d_{i-1}(x,y)\geq k$$$.

There are $$$q$$$ queries. In each query you are given five numbers $$$t,n,k,x,y$$$. You need to output $$$d_{t}(x,y)$$$.

Input

The first line contains one number $$$q$$$ ($$$1\leq q\leq 10^6$$$).

In the following $$$q$$$ lines, there are five numbers $$$t,n,k,x,y$$$ ($$$0\leq t\leq10^9$$$, $$$2\leq n\leq10^9$$$, $$$1\leq k\leq10^9$$$, $$$1\leq x,y\leq n$$$, $$$x\neq y$$$), denoting the query.

Output

For each query, output one line with one number $$$d_{t}(x,y)$$$.

Example
Input
5
1 5 3 2 4
1 10 4 2 4
2 10 5 2 4
1 3 2 1 3
1 3 2 1 2
Output
3
2
-1
1
-1