You are now in a magical land, and you have five different types of sprites around you. The ability value of the $i$-th sprite is $i$.

At this moment, a sprite summoner with a sprite of ability value $6$ passes by. This sprite with an ability value of $6$ looks very powerful, so you quickly ask him how to obtain this kind of sprite and obtain a method called "Link Summon" from him.

Link Summon: Each time, choose some sprites with ability values from $1$ to $5$. For each sprite, you can choose to assign a weight of $1$ or a weight of $x$ ($x$ is its ability value), and then obtain \textbf{one} sprite with the sum of the weights of these sprites. However, due to magical restrictions, the sum of the weights cannot exceed $6$.

Now you want to know how many sprites with an ability value of $6$ you can summon by linking the sprites in your possession.

Input

The first line contains an integer $T$ ($1\le T\le 10^5$), indicating the number of data sets.

Next are $T$ lines, each containing five integers $a_i$ ($0\le a_i \le 10^9,\sum a_i \le 10^9$), indicating the number of sprites you currently have with an ability value of $i$.

Output

For each set of data, output a single integer on a line, indicating the maximum number of sprites with an ability value of $6$ that you can summon through linking.

Example

5
3 3 3 3 3
2 3 4 5 1
1 2 3 4 5
2 2 0 0 0
0 3 0 0 3

7
7
7
1
3