يقوم النادي الدولي للتربيت على الكابيبارا بتحضير قمصان لفعالية ما. توجد أربعة مقاسات هي S و M و L و XL بترتيب تصاعدي. أعداد القمصان المطلوبة هي $n_{\mathrm{S}}$ و $n_{\mathrm{M}}$ و $n_{\mathrm{L}}$ و $n_{\mathrm{XL}}$ على التوالي. عند كثافة اللون القياسية، تتطلب القمصان ذات المقاسات S و M و L و XL كميات قدرها $B$ و $Br$ و $Br^2$ و $Br^3$ وحدة من الصبغة على التوالي.

تستخدم آلة الصباغة كثافة صحيحة $x$. الحد الأدنى المسموح به لكثافة اللون هو $P$، و $x = K$ هي الكثافة القياسية. وبالتالي، يجب أن يحقق $x$ المتباينة $P \le x \le K$. إذا كان القميص يتطلب $q$ وحدة عند الكثافة القياسية، فإن صباغته عند الكثافة $x$ تستهلك $\lceil qx/K \rceil$ وحدة. يجب أن تستخدم جميع القمصان نفس الكثافة $x$.

بإعطائك $A$ وحدة من الصبغة، أوجد أكبر كثافة ممكنة $x$ بحيث يمكن صباغة جميع القمصان دون استخدام أكثر من $A$ وحدة. إذا لم يوجد مثل هذا $x$، فاطبع $-1$.

الإدخال

يحتوي الإدخال على $T$ حالات اختبار. يحتوي السطر الأول على عدد صحيح $T$ ($1 \le T \le 100$)، وهو عدد حالات الاختبار. تتكون كل حالة اختبار من تسعة أعداد صحيحة معطاة بالصيغة التالية:

$$ n_{\mathrm{S}} \ n_{\mathrm{M}} \ n_{\mathrm{L}} \ n_{\mathrm{XL}} \ r \ A \ B \ P \ K $$

تمثل $n_{\mathrm{S}}$ و $n_{\mathrm{M}}$ و $n_{\mathrm{L}}$ و $n_{\mathrm{XL}}$ أعداد القمصان من المقاسات S و M و L و XL على التوالي ($0 \le n_{\mathrm{S}}, n_{\mathrm{M}}, n_{\mathrm{L}}, n_{\mathrm{XL}} \le 10^5$ و $n_{\mathrm{S}} + n_{\mathrm{M}} + n_{\mathrm{L}} + n_{\mathrm{XL}} \ge 1$).

تمثل القيمة $r$ المعامل الذي تزداد به كمية الصبغة المطلوبة عند الكثافة القياسية مع كل زيادة في المقاس ($1 \le r \le 10$).

يمثل $A$ إجمالي كمية الصبغة المتاحة بالوحدات ($0 \le A \le 10^{15}$).

يمثل $B$ كمية الصبغة المطلوبة لصباغة قميص واحد من المقاس S عند الكثافة القياسية بالوحدات ($1 \le B \le 10^6$).

يمثل $P$ الحد الأدنى المسموح به لكثافة اللون، ويمثل $K$ كثافة اللون القياسية ($1 \le P \le K \le 10^9$).

الإخراج

لكل حالة اختبار، اطبع أكبر عدد صحيح $x$ يحقق $P \le x \le K$ بحيث يمكن صباغة جميع القمصان باستخدام $A$ وحدة من الصبغة على الأكثر. إذا لم يوجد مثل هذا العدد الصحيح، فاطبع $-1$.

أمثلة

الإدخال 1

3
1 1 1 1 2 15 2 1 12
2 0 1 0 3 8 2 4 10
0 0 0 1 10 1000 1 900000 999999

الإخراج 1

6
-1
999999