你现在身处一片魔法大陆，并且你身边现在有着五种不同种类的精灵，第 $i$ 种精灵的能力值是 $i$。

这时有个精灵召唤师带着一只能力值为 $6$ 的精灵经过。这个能力值为 $6$ 的精灵看起来十分强大，因此你连忙询问他如何获得这种精灵并从他那获得了一种名为连接召唤的方法。

连接召唤：每次选择一些能力值为 $1$ 到 $5$ 的精灵，对于每只精灵，你可以选择赋权为 $1$ 或者赋权为 $x$（$x$ 为其能力值），然后得到\textbf{一只}能力值为这些精灵赋权和的精灵，但由于魔力限制，赋权和不能超过 $6$。

你现在想知道自己手上的这些精灵能够连接召唤出多少只能力值为 $6$ 的精灵。

Input

第一行一个整数 $T$（$1\le T\le 10^5$），表示数据组数。

接下来 $T$ 行，每行五个整数 $a_i$（$0\le a_i \le 10^9,\sum a_i \le 10^9$），表示你现在具有的能力值为 $i$ 的精灵数量。

Output

对于每组数据，输出一行一个整数，表示你能通过连接召唤得到能力值为 $6$ 的精灵的最大数目。

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