九九归一 · 最少调整

题目背景

Bob 在一家数据公司做后端开发。最近公司上线了一个新的推荐算法，算法要求所有特征权重的乘积必须是 9 的倍数，否则系统会判定配置不合法并自动回滚。

运维给 Bob 下发了一批待调整的特征数组，他可以对任意特征值执行 +1 操作（每次操作将该特征值增加 1）。Bob 想用最少的操作次数让数组达标，好早点下班。

题目描述

给定 t 组测试数据。

每组数据给定一个长度为 n 的数组 a₁, a₂, ..., aₙ。

每次操作可以选择任意一个元素，将其值增加 1。

求使所有元素的乘积 ∏aᵢ 被 9 整除所需的最少操作次数。

数学背景：乘积被 9 整除 ⇔ 乘积的质因数分解中 3 的指数 ≥ 2。

输入格式

第一行一个整数 t（1 ≤ t ≤ 10⁴），表示测试数据组数。

每组测试数据：

• 第一行一个整数 n（1 ≤ n ≤ 2×10⁵）。
• 第二行 n 个整数 a₁, a₂, ..., aₙ（0 ≤ aᵢ ≤ 10⁹）。

保证所有测试数据的 n 之和不超过 2×10⁵。

输出格式

对于每组测试数据，输出一行一个整数，表示最小操作次数。

样例

5
3
2 5 7
2
4 8
1
10
4
6 10 12 13
5
0 1 2 3 4

2
1
8
0
0

样例说明：

• 第一组：[2,5,7]，a₁+1=3，a₂+1=6 → [3,6,7]，乘积 126 = 9×14。操作 2 次。
• 第二组：[4,8]，a₂+1=9 → [4,9]，乘积 36 = 9×4。操作 1 次。
• 第三组：[10]，加 8 次 → [18]，乘积 18 = 9×2。操作 8 次。
• 第四组：[6,10,12,13]，乘积 9360 = 9×1040，已满足。操作 0 次。
• 第五组：含 0，乘积为 0，0 被任何数整除。操作 0 次。

数据范围

• 1 ≤ t ≤ 10⁴
• 1 ≤ n ≤ 2×10⁵，∑n ≤ 2×10⁵
• 0 ≤ aᵢ ≤ 10⁹