Welcome to Summer Rift! Summer Rift is a modern city. Its roads run either north-south or east-west and therefore the whole city looks like a grid table. As a result, every intersection in Summer Rift can be identified by a pair of integer (x, y), 0<=x<=n, 0<=y<=m.
Garen is a Summer Rift citizen and lives at intersection (0, 0). Every day he is going to visit Lux, who is living at intersection (n, m), and fight with her. Garen don't want to waste time, so he needs to follow a shortest route from (0, 0) to (n, m). In other words, if Garen is at intersection (x, y) on his way to Lux's place, he can only go to (x+1, y) or (x, y +1) in the next step. Now Garen wonders that how many routes he can choose.
Oh, that's too easy, right?
Summer Rift is also a dangerous city. There're many rampage enemies that slay, double-kill or triple-kill other citizens. So every day the police will block a rectangle region which is represented as (x1, y1, x2, y2). All intersections (x, y) that satisfy x1<=x <=x2 and y1<=y<=y2 are dangerous this day.
Every day Garen receives the blocked region (x1, y1, x2, y2) of that day before he visits Lux. Now Garen wonders how many routes he can choose to visit Lux without passing through any dangerous intersection during the tour?
The first line of input contains an integer T, the number of test cases in total.
The first line of each test case contains three integers n; m; d, the size of Summer Rift and the number of considered days. Each of following d lines contains four integers (x1, y1, x2, y2) which is the representation of the blocked region of that day.
1<=T<=25
1<=n,m<=2000
1<=d<=2*10^5
0<=x1<=x2<=n, 0<=y1<=y2<=m
Print the number of routes module 10007 for each day, one day per line.