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 \le i < 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 \ge 1$), there’s an edge between $x$ and $y$ if and only if $d_{i-1}(x, y) \ge 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 \le q \le 10^6$).

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

Output

For each query, output one line with one number $d_t(x, y)$.

Examples

Input 1

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 1

3
2
-1
1
-1