Little L likes planting trees.

Little L planted $d$ trees on both the left and right sides of the yard. On the left side, the $i$-th tree has a height of $x_i$ meters on the first day and grows $f_i$ meters each day. On the right side, the $i$-th tree has a height of $y_i$ on the first day and grows $g_i$ meters each day.

However, Little L does not want the trees to be too high. To keep things neat, for the tree numbered $i$, if its height reaches or exceeds $m_i$, he will prune it by $m_i$ meters until its height is less than $m_i$.

Now, Little L wants to know, for the tree numbered $i$, during the first $n_i$ days after planting, after performing pruning each day, how many days the left tree is shorter than the right tree.

Note: pruning is also performed on the first day.

Input

There is only one test case in each test file.

The first line contains a positive integer $d$ ($1 \le d \le 10^4$), denoting the number of trees on each side of the yard.

Each of the next $d$ lines contains six positive integers $f_i, x_i, g_i, y_i, n_i, m_i$ ($1 \le f_i, x_i, g_i, y_i, n_i, m_i \le 10^6$), with the meanings described above.

Output

Output $d$ lines, each line containing a non-negative integer, representing the number of days within $n_i$ days that the left tree is shorter than the right tree for the tree numbered $i$.

Example

Sample Input 1

1
7 4 6 3 3 4

Sample Output 1

2

Note

For the first sample, we count the first $3$ days:

Day $1$: The initial height of the tree on the left side of the road is $4$ meters, and the tree on the right is $3$ meters. The left tree exceeds the $4$-meter limit, so it is pruned. After pruning, the left tree is $0$ meters and the right tree is $3$ meters; the left is lower than the right.

Day $2$: The left tree is $7$ meters and the right tree is $9$ meters. They both exceed $4$ meters, so they are pruned. After pruning, the left tree is $3$ meters and the right tree is $1$ meter; the left is not lower than the right.

Day $3$: The left tree is $10$ meters and the right tree is $7$ meters. They both exceed $4$ meters, so they are pruned. After pruning, the left tree is $2$ meters and the right tree is $3$ meters; the left is lower than the right.

Therefore, the output is $2$.