Маленький L любит сажать деревья.

Маленький L посадил по $d$ деревьев с левой и с правой стороны двора. С левой стороны $i$-е дерево в первый день имеет высоту $x_i$ метров и вырастает на $f_i$ метров каждый день. С правой стороны $i$-е дерево в первый день имеет высоту $y_i$ и вырастает на $g_i$ метров каждый день.

Однако Маленький L не хочет, чтобы деревья были слишком высокими. Чтобы поддерживать порядок, для дерева с номером $i$, если его высота достигает или превышает $m_i$, он обрезает его на $m_i$ метров до тех пор, пока его высота не станет меньше $m_i$.

Теперь Маленький 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$ строк, каждая из которых содержит неотрицательное целое число — количество дней из $n_i$ дней, в которые левое дерево ниже правого для дерева с номером $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$.