시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 392 135 61 29.612%

문제

상근이는 위성 사진 여러장을 이용해서 지도를 만들고 있다. 위성에는 카메라가 달려있고, 카메라는 한 영역을 찍는다. 이러한 위성 사진 여러 장을 합치면, 큰 사진을 만들 수 있다.

위성 사진 여러 장이 주어졌을 때, 사진이 찍힌 영역의 넓이를 구하는 프로그램을 작성하시오. 사진은 모두 직사각형이다. 한 영역이 여러 사진에 찍혀있을 수도 있다. 이런 경우에 그 영역의 넓이는 한 번만 더해야 한다.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 수는 100개를 넘지 않는다.

각 테스트 케이스의 첫째 줄에는 사진의 수 n (1 ≤ n ≤ 1000)이 주어진다. 다음 n개 줄에는 위성 사진의 남서쪽과 복동쪽 꼭짓점을 나타내는 네 정수 x1, y1, x2, y2가 주어진다. (0 ≤ x1, y1, x2, y2 ≤ 1,000,000, x1 < x2, y1 < y2) 모든 위성 사진은 직사각형이고, 다른 두 꼭짓점은 (x1, y2)와 (x2, y1) 이다.

모든 좌표는 이차원 평면 위에 있으며, 지구는 평면이라고 가정한다.

출력

각 테스트 케이스마다 위성 사진이 찍은 전체 영역의 넓이를 출력한다.

예제 입력 1

2
3
0 6 20 16
14 0 24 10
50 50 60 60
2
0 0 20 10
10 4 14 8

예제 출력 1

376
200
W3sicHJvYmxlbV9pZCI6IjkzMTgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM3MDRcdWMxMzEgXHVjMGFjXHVjOWM0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjNzA0XHVjMTMxIFx1YzBhY1x1YzljNCBcdWM1ZWNcdWI3ZWNcdWM3YTVcdWM3NDQgXHVjNzc0XHVjNmE5XHVkNTc0XHVjMTFjIFx1YzljMFx1YjNjNFx1Yjk3YyBcdWI5Y2NcdWI0ZTRcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWM3MDRcdWMxMzFcdWM1ZDBcdWIyOTQgXHVjZTc0XHViYTU0XHViNzdjXHVhYzAwIFx1YjJlY1x1YjgyNFx1Yzc4OFx1YWNlMCwgXHVjZTc0XHViYTU0XHViNzdjXHViMjk0IFx1ZDU1YyBcdWM2MDFcdWM1ZWRcdWM3NDQgXHVjYzBkXHViMjk0XHViMmU0LiBcdWM3NzRcdWI3ZWNcdWQ1NWMgXHVjNzA0XHVjMTMxIFx1YzBhY1x1YzljNCBcdWM1ZWNcdWI3ZWMgXHVjN2E1XHVjNzQ0IFx1ZDU2OVx1Y2U1OFx1YmE3NCwgXHVkMDcwIFx1YzBhY1x1YzljNFx1Yzc0NCBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzA0XHVjMTMxIFx1YzBhY1x1YzljNCBcdWM1ZWNcdWI3ZWMgXHVjN2E1XHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YzBhY1x1YzljNFx1Yzc3NCBcdWNjMGRcdWQ3OGMgXHVjNjAxXHVjNWVkXHVjNzU4IFx1YjExM1x1Yzc3NFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC4gXHVjMGFjXHVjOWM0XHVjNzQwIFx1YmFhOFx1YjQ1MCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NzRcdWIyZTQuIFx1ZDU1YyBcdWM2MDFcdWM1ZWRcdWM3NzQgXHVjNWVjXHViN2VjIFx1YzBhY1x1YzljNFx1YzVkMCBcdWNjMGRcdWQ2MDBcdWM3ODhcdWM3NDQgXHVjMjE4XHViM2M0IFx1Yzc4OFx1YjJlNC4gXHVjNzc0XHViN2YwIFx1YWNiZFx1YzZiMFx1YzVkMCBcdWFkZjggXHVjNjAxXHVjNWVkXHVjNzU4IFx1YjExM1x1Yzc3NFx1YjI5NCBcdWQ1NWMgXHViYzg4XHViOWNjIFx1YjM1NFx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWMyMThcdWIyOTQgMTAwXHVhYzFjXHViOTdjIFx1YjExOFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjMGFjXHVjOWM0XHVjNzU4IFx1YzIxOCBuICgxICZsZTsgbiAmbGU7IDEwMDApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMmU0XHVjNzRjIG5cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YzcwNFx1YzEzMSBcdWMwYWNcdWM5YzRcdWM3NTggXHViMGE4XHVjMTFjXHVjYWJkXHVhY2ZjIFx1YmNmNVx1YjNkOVx1Y2FiZCBcdWFmMmRcdWM5ZDNcdWM4MTBcdWM3NDQgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1YjEyNCBcdWM4MTVcdWMyMTggeDxzdWI+MTxcL3N1Yj4sIHk8c3ViPjE8XC9zdWI+LCB4PHN1Yj4yPFwvc3ViPiwgeTxzdWI+MjxcL3N1Yj5cdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMCAmbGU7IHg8c3ViPjE8XC9zdWI+LCB5PHN1Yj4xPFwvc3ViPiwgeDxzdWI+MjxcL3N1Yj4sIHk8c3ViPjI8XC9zdWI+ICZsZTsgMSwwMDAsMDAwLCB4PHN1Yj4xPFwvc3ViPiAmbHQ7IHg8c3ViPjI8XC9zdWI+LCB5PHN1Yj4xPFwvc3ViPiAmbHQ7IHk8c3ViPjI8XC9zdWI+KSBcdWJhYThcdWI0ZTAgXHVjNzA0XHVjMTMxIFx1YzBhY1x1YzljNFx1Yzc0MCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NzRcdWFjZTAsIFx1YjJlNFx1Yjk3OCBcdWI0NTAgXHVhZjJkXHVjOWQzXHVjODEwXHVjNzQwICh4PHN1Yj4xPFwvc3ViPiwgeTxzdWI+MjxcL3N1Yj4pXHVjNjQwICh4PHN1Yj4yPFwvc3ViPiwgeTxzdWI+MTxcL3N1Yj4pIFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYWE4XHViNGUwIFx1Yzg4Y1x1ZDQ1Y1x1YjI5NCBcdWM3NzRcdWNjMjhcdWM2ZDAgXHVkM2M5XHViYTc0IFx1YzcwNFx1YzVkMCBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1YzljMFx1YWQ2Y1x1YjI5NCBcdWQzYzlcdWJhNzRcdWM3NzRcdWI3N2NcdWFjZTAgXHVhYzAwXHVjODE1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0IFx1YzcwNFx1YzEzMSBcdWMwYWNcdWM5YzRcdWM3NzQgXHVjYzBkXHVjNzQwIFx1YzgwNFx1Y2NiNCBcdWM2MDFcdWM1ZWRcdWM3NTggXHViMTEzXHVjNzc0XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI5MzE4IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQXJlYSBDb3ZlcmFnZSIsImRlc2NyaXB0aW9uIjoiPHA+SW4gdGhpcyBkYXkgYW5kIGFnZSwgYSBsb3Qgb2YgdGhlIHNweWluZyBvbiBvdGhlciBjb3VudHJpZXMgaXMgZG9uZSB3aXRoIHRoZSB1c2Ugb2Ygc2F0ZWxsaXRlcyBhbmQgZHJvbmVzIGVxdWlwcGVkIHdpdGggY2FtZXJhcy4gQWxsIHRoZXNlIHBob3RvZ3JhcGhzIG9mIHZhcmlvdXMgc2l6ZXMgYW5kIGZyb20gdmFyaW91cyBzb3VyY2VzIGNhbiBiZSBjb21iaW5lZCB0byBnaXZlIGEgcGljdHVyZSBvZiB0aGUgY291bnRyeSBhcyBhIHdob2xlLjxcL3A+XHJcblxyXG48cD5HaXZlbiB0aGUgcGhvdG9ncmFwaHMgKHRoYXQgaXMgdG8gc2F5LCB0aGUgcmVjdGFuZ3VsYXIgYXJlYSBjb3ZlcmVkIGJ5IGVhY2gsIHNpbmNlIHRoZSBjb250ZW50cyBvZiB0aGUgcGhvdG9ncmFwaHMgdGhlbXNlbHZlcyBhcmUgb2YgY291cnNlIHRvcC1zZWNyZXQhKSwgY2FuIHlvdSB3b3JrIG91dCB3aGF0IHRoZSB0b3RhbCBhcmVhIGlzIG9mIGFsbCB0aGF0IGlzIHBob3RvZ3JhcGhlZD8gTm90ZSB0aGF0IGNlcnRhaW4gYXJlYXMgY2FuIGFwcGVhciBvbiBtdWx0aXBsZSBwaG90b2dyYXBocyBhbmQgc2hvdWxkIGJlIGNvdW50ZWQgb25seSBvbmNlLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+T24gdGhlIFx1ZmIwMXJzdCBsaW5lIG9uZSBwb3NpdGl2ZSBudW1iZXI6IHRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcywgYXQgbW9zdCAxMDAuIEFmdGVyIHRoYXQgcGVyIHRlc3QgY2FzZTo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5vbmUgbGluZSB3aXRoIGFuIGludGVnZXIgbiAoMSAmbGU7IG4gJmxlOyAxIDAwMCk6IHRoZSBudW1iZXIgb2YgcGhvdG9ncmFwaHMuPFwvbGk+XHJcblx0PGxpPm4gbGluZXMgd2l0aCBmb3VyIHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2VycyB4PHN1Yj4xPFwvc3ViPiwgeTxzdWI+MTxcL3N1Yj4sIHg8c3ViPjI8XC9zdWI+IGFuZCB5PHN1Yj4yPFwvc3ViPiAoMCAmbGU7IHg8c3ViPjE8XC9zdWI+LCB5PHN1Yj4xPFwvc3ViPiwgeDxzdWI+MjxcL3N1Yj4sIHk8c3ViPjI8XC9zdWI+ICZsZTsgMSAwMDAgMDAwLCB4PHN1Yj4xPFwvc3ViPiAmbHQ7IHg8c3ViPjI8XC9zdWI+IGFuZCB5PHN1Yj4xPFwvc3ViPiAmbHQ7IHk8c3ViPjI8XC9zdWI+KTogdGhlIGNvb3JkaW5hdGVzIG9mIHRoZSBzb3V0aHdlc3QgYW5kIG5vcnRoZWFzdCBjb3JuZXIsIHJlc3BlY3RpdmVseSwgb2YgZWFjaCBwaG90b2dyYXBoLiBUaGUgcGhvdG9ncmFwaHMgYXJlIGFsbCByZWN0YW5ndWxhciBpbiBzaGFwZSB3aXRoIHRoZWlyIG90aGVyIGNvcm5lcnMgYXQgKHg8c3ViPjE8XC9zdWI+LCB5PHN1Yj4yPFwvc3ViPikgYW5kICh4PHN1Yj4yPFwvc3ViPiwgeTxzdWI+MTxcL3N1Yj4pLjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlRoZSBjb29yZGluYXRlcyBjb3JyZXNwb25kIHRvIGEgXHVmYjAyYXQgdHdvLWRpbWVuc2lvbmFsIHNwYWNlIChpLmUuIHdlIGFzc3VtZSB0aGUgRWFydGggdG8gYmUgXHVmYjAyYXQpLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlBlciB0ZXN0IGNhc2U6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+b25lIGxpbmUgd2l0aCBhbiBpbnRlZ2VyOiB0aGUgdG90YWwgYXJlYSBvZiBhbGwgdGhhdCBhcHBlYXJzIG9uIHRoZSBwaG90b2dyYXBocy48XC9saT5cclxuPFwvdWw+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==