## EXPAND - Barn Expansion

Farmer John has N (1 <= N <= 25,000) rectangular barns on his farm, all with sides parallel to the X and Y axes and integer corner coordinates in the range 0..1,000,000. These barns do not overlap although they may share corners and/or sides with other barns. Since he has extra cows to milk this year, FJ would like to expand some of his barns. A barn has room to expand if it does not share a corner or a wall with any other barn. That is, FJ can expand a barn if all four of its walls can be pushed outward by at least some amount without bumping into another barn. If two barns meet at a corner, neither barn can expand. Please determine how many barns have room to expand.

### Input

t – the number of test cases, then t test cases follow.

Each test case takes the following form:

The first line contains the number of rectangular barns - n.

Each of the next n lines contains:

Four space-separated integers A, B, C, and D, describing one barn. The lower-left corner of the barn is at (A,B) and the upper right corner is at (C,D).

### Output

For each test case write a single integer that is the number of barns that can be expanded in a separate line

### Example

Input:1 5 0 2 2 7 3 5 5 8 4 2 6 4 6 1 8 6 0 0 8 1Output:2

**Input/Output details:**

There are 5 barns. The first barn has its lower-left corner at (0,2) and its upper-right corner at (2,7), and so on.

Only two barns can be expanded --- the first two listed in the input. All other barns are each in contact with at least one other barn.

Added by: | Nguyen Dinh Tu |

Date: | 2006-01-17 |

Time limit: | 0.990s |

Source limit: | 50000B |

Memory limit: | 1536MB |

Cluster: | Cube (Intel G860) |

Languages: | All except: NODEJS PERL6 VB.NET |

Resource: | USACO December 2005 Gold Division |