你有四个整数序列 $a_1, a_2, \dots, a_n$；$b_1, b_2, \dots, b_n$；$x_1, x_2, \dots, x_n$；$y_1, y_2, \dots, y_n$。 让我们构建一个有向图，如果 $i < j$ 且 $a_i \cdot x_j + b_i \ge y_j$，则图中存在一条从 $i$ 到 $j$ 的边。 你需要找到该图中的最长路径。

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 300\,000$)：测试用例的数量。 每个测试用例的第一行包含一个整数 $n$ ($1 \le n \le 150\,000$)：序列中整数的数量。 接下来的 $n$ 行，每行包含四个整数 $a_i, b_i, x_i, y_i$ ($0 \le a_i, x_i \le 300\,000; 0 \le b_i, y_i \le 10^{11}$)。 保证所有测试用例的 $n$ 之和不超过 $300\,000$。

输出格式

对于每个测试用例，输出一个整数：描述图中的最长路径长度。

样例

输入 1

3
3
1 1 1 1
2 2 2 2
3 3 3 3
3
1 1 1 1
2 2 2 10
3 3 3 100
1
35 35 35 35

输出 1

3
1
1