Cho ~n~ hình chữ nhật, hình thứ ~i~ có chiều dài ~a_i~ và chiều rộng ~b_i~.

Bạn được xoay các hình chữ nhật tùy ý. Hãy tìm ra hình chữ nhật có diện tích nhỏ nhất, mà có thể xếp ~n~ hình chữ nhật trên vào hình chữ nhật lớn này, sao cho ~n~ hình chữ nhật đó không chồng lền nhau.

INPUT

Dòng đầu tiên chứa số nguyên dương ~t~ (~1 \le t \le 1000~) là số lượng test.

Mỗi test gồm:

• Dòng đầu tiên chứa hai số nguyên dương ~n~ (~1 \le n \le 3~) là số hình chữ nhật.
• ~n~ dòng tiếp theo, mỗi dòng gồm hai số nguyên dương ~a_i, b_i~ (~1 \le a_i, b_i \le 10^9~) mô tả một hình chữ nhật.

OUTPUT

Với mỗi test, in ra diện tích hình chữ nhật nhỏ nhất tìm được trên một dòng.

SAMPLE INPUT

3
1
4 4
2
3 5 
2 6
3
3 7
1 8
4 9

SAMPLE OUTPUT

16
30
68