数字卡片

Problem Description

你有一些写有 $0,1,\ldots,9$ 的数字卡片，其中写有数字 $i$ 的卡片共 $a_i$ 张。 你可以把任意多张 $6$ 变成 $9$，也可以把任意多张 $9$ 变成 $6$。 如果每张卡片只能使用一次，那么你用这些卡片至多能拼出多少个 $4$ 的倍数？

Input

本题有多组测试数据。 输入的第一行有一个正整数 $T$（$1\le T\le 100$），表示数据组数。 之后 $T$ 行，每行有 $10$ 个自然数 $a_0,a_1,\ldots, a_9$（$0\le a_i \le 10^9$），依次表示每种卡牌的数量。

Output

对于每组测试数据输出一行一个自然数表示答案。

Sample Input

1
1 1 2 0 0 0 1 0 0 0

Sample Output

3

Hint

你手上的卡牌有 $0,1,2,2,6$ 共五张。 你可以把 $6$ 变成 $9$，然后拼成 $0,12,92$ 这三个 $4$ 的倍数。

Source

2025“钉耙编程”中国大学生算法设计暑期联赛（9）