Ada the Ladybug works as farmer. Its season of cucumbers and she wants to harvest them. There lies many cucumbers all around her house. She wants to choose a direction and follow it until all cucumbers in that direction are collected. Lets consider Ada's house as centerpiece of whole universe, lying on [0,0]. The cucumbers are defined as lines on plane. No cucumber goes through Ada's house (and no cucumber touches it). How many cucumbers can Ada pick in one go if she chooses the best direction possible? Input The first line contains an integer T, the number of test-cases. Each test-case begins with an integer 1 ≤ N ≤ 105 Afterward N lines follow, with four integers -106 ≤ x1,y1,x2,y2 ≤ 106, the beginning and end of each cucumber. Each cucumber has positive length. Sum of all N over all test-cases won't exceed 106 Even though cucumber will not go through house, they might touch, intersect or overlap other cucumbers! Output For each test-case print one integer - the maximal number of cucumbers which could be picked if Ada chooses a direction and picks every cucumber lying in it.

这道题目可以使用计算几何中的极角排序来解决。

首先，将每个黄瓜线段表示成起点和终点之间的向量，然后将它们按照极角排序。这可以通过计算每个向量的极角来完成，然后使用 STL 的 sort 函数进行排序。

接下来，在排序后的向量中，找到一个连续的子序列，使得这些向量的极角在某个范围内。我们可以使用双指针来实现这一步。具体来说，我们可以从极角最小的向量开始，逐个向右移动右指针，直到极角超过了某个范围。然后，我们将左指针向右移动一位，并检查新的子序列是否仍然在范围内。我们重复这个过程，直到右指针到达向量的末尾。

最终，我们可以找到一个包含最多黄瓜线段的子序列，它们都在某个范围内。这些线段在同一方向上，因此可以一次性收集它们。

以下是参考代码：