QC CZ情定三生之一起来看流星雨

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

 

刚才的故事结束以后,CZ在城堡的残骸中找到了奄奄一息的QC。正当CZ拿起菜刀要斩杀QC之时,QC醒了过来,说出了他50多年以来内心的秘密,他一直深深爱着他的老冤家CZ。QC说,我一直跟你作对你难道看不出来我只是为了让你多看一眼么??!!我一直嗯哼你,但你却一直不明白我的意思,我这几年一直在找你,就是为了向对你说一句别闹了,但是当我得到你的消息的时候,我却得知你竟然娶了凤姐!!!!虽然她比我更加貌美如花,但是我们才是青梅竹马啊!CZ说,现在说这些有用么,呵呵。CZ果断举起了菜刀,然后回头砍死了凤姐,“T**(和谐),早想休了你了,川川,我来了~”~

他们手牵手,一起消失在了夜空下。这时下起了流星雨,QC拿起了相机说,“在流星雨中记录下我们的幸福生活,以后我们会一起又看流星雨,一起再看流星雨,一起还看流星雨,一起老看流星雨的”~

他们的相机时矩形的,他们已知n个流星的初始位置和速度,他们想在某时刻照下最多的流星。注意,在相机边界上不会被照到。相机的左下角为(0,0),右上角为(w,h).每个流星用两个向量p,v,表示,其中,p为初速度(t = 0时)位置,v为速度。在时刻t(t>=0)的位置是p+tv。比如,若p = (1,3),v= (-2,5),则t = 0.5时该流星的位置为(1,3)+0.5*(-2,5) = (0,5.5)。

Input

 

输入测试组数 T。每组数据的第一行为两个整数w和h(1, <= w,h <= 100 000);第二行为流星个数n(1 <= n <= 100 000);以下n行每行都用4个整数xi,yi,ai,bi时速度,ai和bi不同时为0.不同流星的初始位置不同。

Output

 

对于每组数据,输出能找到的流星个数的最大值。

Sample Input

2
2 2
4
-9 -3 -7 -4
7 -3 -7 10
3 -6 -4 3
-7 -6 4 -2
4 1
3
1 2 10 -7
-9 -9 -10 -2
-5 1 -2 -1

Sample Output

0
1

Hint

 

Source

zyj