מועדון ליטוף הקפיברות הבינלאומי מכין חולצות טי לאירוע. ישנן ארבע מידות, 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