+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- روی یک میز، $n$ کاغذ قرار دارد. هر کاغذ به صورت یک مستطیل است. هر با می‌توانیم با کمک یک تیغ، یک خط راست روی میز بکشیم. می‌خواهیم با کمک این خطوط، همه‌ی کاغذها را نصف کنیم. (مهم نیست یک کاغذ چندبار رویش تیغ کشیده شود مهم این است که برشی باشد که آن را نصف کند.) # ورودی در سطر اول ورودی، عدد صحیح $t$ آمده که تعداد سناریوها را نشان می‌دهد. $$1 \leq t \leq 100$$ در سطر اول هر سناریو، عدد صحیح $n$ آمده که تعداد کاغذها را نشان می‌دهد. $$1 \leq n \leq 14$$ در $n$ سطر بعدی، در هر سطر ۸ عدد $x_1, y_1, x_2, y_2, x_3, y_3, x_4, y_4\quad$ می‌آیند که مختصات چهار گوشه‌ی کاغذ را نشان می‌دهد. $$-100 \leq x_1, y_1, x_2, y_2, x_3, y_3, x_4, y_4 \leq 100$$ # خروجی به ازای هر سناریو، حداقل تعداد برش را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 1 5 15 15 15 25 25 25 25 15 25 25 25 35 35 35 35 25 35 35 35 45 45 45 45 35 15 35 15 45 25 45 25 35 35 15 35 25 45 25 45 15 ``` ## خروجی نمونه ۱ ``` 2 ```