Little L은 나무 심기를 좋아합니다.

Little L은 마당의 왼쪽과 오른쪽에 각각 $d$그루의 나무를 심었습니다. 왼쪽에서 $i$번째 나무는 첫째 날의 높이가 $x_i$미터이고 매일 $f_i$미터씩 자랍니다. 오른쪽에서 $i$번째 나무는 첫째 날의 높이가 $y_i$이고 매일 $g_i$미터씩 자랍니다.

하지만 Little L은 나무가 너무 높아지는 것을 원치 않습니다. 깔끔하게 유지하기 위해 번호가 $i$인 나무의 높이가 $m_i$ 이상이 되면, 높이가 $m_i$ 미만이 될 때까지 $m_i$미터씩 가지치기를 합니다.

이제 Little L은 번호가 $i$인 나무에 대해, 나무를 심은 후 처음 $n_i$일 동안 매일 가지치기를 수행한 뒤 왼쪽 나무가 오른쪽 나무보다 더 낮은 날이 며칠인지 알고 싶어 합니다.

참고: 첫째 날에도 가지치기를 수행합니다.

입력

각 테스트 파일에는 테스트 케이스가 하나만 있습니다.

첫째 줄에 마당의 각 편에 심어진 나무의 수를 나타내는 양의 정수 $d$ ($1 \le d \le 10^4$)가 주어집니다.

다음 $d$개의 줄에는 각각 위에서 설명한 의미를 갖는 여섯 개의 양의 정수 $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$)가 주어집니다.

출력

$d$개의 줄을 출력합니다. 각 줄에는 번호가 $i$인 나무에 대해 $n_i$일 동안 왼쪽 나무가 오른쪽 나무보다 더 낮은 날의 수를 나타내는 음이 아닌 정수를 출력합니다.

예제

예제 입력 1

1
7 4 6 3 3 4

예제 출력 1

2

노트

첫 번째 예제에서는 처음 $3$일을 셉니다:

$1$일차: 길 왼쪽 나무의 초기 높이는 $4$미터이고, 오른쪽 나무는 $3$미터입니다. 왼쪽 나무가 $4$미터 제한에 도달했으므로 가지치기를 합니다. 가지치기 후 왼쪽 나무는 $0$미터, 오른쪽 나무는 $3$미터가 되어 왼쪽이 오른쪽보다 낮습니다.

$2$일차: 왼쪽 나무는 $7$미터이고 오른쪽 나무는 $9$미터입니다. 둘 다 $4$미터를 초과하므로 가지치기를 합니다. 가지치기 후 왼쪽 나무는 $3$미터, 오른쪽 나무는 $1$미터가 되어 왼쪽이 오른쪽보다 낮지 않습니다.

$3$일차: 왼쪽 나무는 $10$미터이고 오른쪽 나무는 $7$미터입니다. 둘 다 $4$미터를 초과하므로 가지치기를 합니다. 가지치기 후 왼쪽 나무는 $2$미터, 오른쪽 나무는 $3$미터가 되어 왼쪽이 오른쪽보다 낮습니다.

따라서 출력은 $2$입니다.