There are $t$ queries. Each query provides four integers $l, r, n, m$. Determine how many integers $i \in [l, r]$ satisfy the condition that there exist two integers $0 \le u \le n$ and $0 \le v \le m$ such that $i = \binom{u}{v}$. Here, $\binom{u}{v}$ is defined as: if $u \ge v$, then $\binom{u}{v} = \frac{u!}{v!(u-v)!}$. Otherwise, $\binom{u}{v} = 0$.

Input

The first line contains an integer $t$ ($1 \le t \le 10^5$). The next $t$ lines each contain four integers $l, r, n, m$, describing a query ($1 \le l, r, n, m \le 10^9, r \ge l$).

Output

For each query, output a single integer on a new line representing the answer.

Examples

Input 1

2
1 6 4 2
30 60 9 3

Output 1

5
3