A filled pancake consists of a pancake and its filling. In this problem, you will be given a list of ingredients you have and your task is to prepare as many filled pancakes as possible.

Given 8 cups of milk, 8 egg yolks, 4 tablespoons of sugar, 1 teaspoon of salt, and 9 cups of flour, we can prepare 16 pancakes. For the purpose of this problem, we assume that these quantities scale arbitrarily: for any x ≥ 0, if you have x times as much of every ingredient, you can prepare ⌊16x⌋ pancakes.

Given the necessary ingredients, you can prepare the following fillings:

- banana pancake: 1 banana
- strawberry pancake: 30 g of strawberry jam
- chocolate pancake: 25 g of chocolate spread
- walnut pancake: 10 walnuts
- ⋆ banana pancake with chocolate: 3/4 of a banana, 10 g of chocolate spread
- ⋆ walnut pancake with chocolate: 7 walnuts, 10 g of chocolate spread
- ⋆ grand mix pancake: 1/3 of a banana, 3 walnuts, 5 g of strawberry jam, and 5 g of chocolate spread

Banana pieces can be combined. For example, you can use three pieces of 1/3 banana each to create a banana pancake. For the easy subproblem, ignore the pancakes marked by a star.

Input specification

The first line of the input file contains an integer t specifying the number of test cases. Each test case is preceded by a blank line. Each test case consists of two lines.

The first line of a test case contains five integers c_{m}, y, s_{su}, s_{sa}, and f, meaning that you have c_{m} cups of
milk, y egg yolks, s_{su} tablespoons of sugar, s_{sa} teaspoons of salt, and f cups of flour.

The second line contains four integers b, g_{s}, g_{c}, and w, meaning that you have b bananas, g_{s} grams of
strawberry jam, g_{c} grams of chocolate spread, and w walnuts.

All quantities are between 0 and 10^{6}, inclusive.

Output specification

For each test case, output a single line containing a single integer – the maximum number of filled pancakes you can prepare.

Example for the easy subtask

input

2

16 16 8 2 17

10 47 100 19

16 16 8 2 17

10 470 100 19

16 16 8 2 17

10 47 100 19

16 16 8 2 17

10 470 100 19

output

16

30

30

In the first test case, we are limited by the number of fillings: we can make 10 banana pancakes, 1 strawberry pancake, 4 chocolate pancakes, and 1 walnut pancake. In the second test case, we only have enough flour for 30 pancakes.

If we solved the same input in the hard subtask, the first answer would be 17: First, make 3 grand mix pancakes. You are left with 9 bananas, 32 g of strawberry jam, 85 g of chocolate spread, and 10 walnuts. That is enough for another 9+1+3+1=14 easy pancakes.