• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

الکس تاو (Alex Tew) یک ایده بسیار جالب دارد و می‌توانید ماجرای اصلی آن را اینجا بخوانید. اما داستان تحریف شده آن را در ادامه آورده‌ایم.

او در صفحه اول یک وب‌سایت یک بنر $n \times m$ پیکسل قرار داده است. او قیمت هر پیکسل را یک دلار قرار داده است.

اما او یک قانون دارد، آن هم این که هر کس می‌تواند یک بلوک $a \times b$ از این صفحه را بخرد که قبلا هیچ پیکسلی از آن به فروش نرسیده باشد.

حال امین می‌خواهد تعدادی از پیکسل‌ها را بخرد به طوری که:

• هیچ کس نتواند هیچ پیکسل دیگری بخرد.
• کمترین هزینه را صرف این کار کند.

ورودی

در سطر اول ورودی، عدد صحیح $T$ آمده، که تعداد تست‌کیس‌ها را نشان‌می‌دهد. $$1 \leq T \leq 100$$

در $T$ سطر بعدی، در هر سطر چهار عدد صحیح $n$، $m$، $a$ و $b$ آمده که به ترتیب تعداد سطر و ستون‌های سایت و ابعاد بلوک‌های مجاز برای خریدن است.

$$1 \leq a \leq n \leq 1000, \quad \quad 1 \leq b \leq m \leq 1000$$

خروجی

خروجی $T$ سطر دارد که کمترین تعداد بلوک لازم برای رسیدن به هدف امین را نشان می‌دهد.

مثال

ورودی نمونه ۱

3
5 7 1 1
10 10 2 3
5 7 2 1

خروجی نمونه ۱

35
6
14

تست اول.

اگر صفحه اصلی $5\times7$ باشد و امکان خرید بلوک‌های $1\times1$ باشد، باید همه $35$ خانه را بخرد تا کسی نتواند هیچ بلوک دیگری را بخرد.

تست دوم.

اگر صفحه اصلی $10\times10$ باشد و امکان خرید بلوک‌های $2\times 3$ باشد‌، می‌تواند با خریدن $6$ بلوک مانند تصویر پایین‌، کاری کند که هیچ‌کس نتواند بلوک دیگری بخرد. همچنین می‌توان نشان‌داد حداقل $6$ بلوک لازم است.

تست سوم.

اگر صفحه اصلی $5\times7$ باشد و امکان خرید بلوک‌های $2\times 1$ باشد‌، می‌تواند با خریدن $14$ بلوک مانند تصویر پایین‌، کاری کند که هیچ‌کس نتواند بلوک دیگری بخرد. همچنین می‌توان نشان‌داد حداقل $14$ بلوک لازم است.