小明有n个数字（均是0-9中的数字），希望把它们拼成一个数字。小明可以不使用其中的若干数字，但是他希望这个数字是9的倍数，并且尽可能的大，小明想知道这个数字是多少。

如果无论如何都不能组成9的倍数，那么输出0即可。如果有前导0，那么输出时删除这些前导0。

每个测试点有多组测试数据。

输入的第一行包含一个数字t，表示测试数据的组数。接下来有2t行，每两行表示一组测试数据。

每组测试数据的第一行包含一个数字n。表示数字的个数。

每组测试数据的第二行包含n个数字$a{1},a{2},\ldots ,a_{n}$，它们均是0-9的数字。

每组测试数据输出一行，包含一个数字，即最大的9的倍数。

样例1解释

1、2、3、3组成的最大数字就是3321，它正好是9的倍数。 

1、1、4、5、1、4可以组成的9的倍数有：45、54、144、414、441。其中441最大。

数据范围

对于所有测试数据有：$1≤t≤10,\sum{n} \leq 5\times {10}^{5}。 |测试点| n≤| 特殊性质| |-----|-----|-----| |1| 1| 无| |2~4| 6| 无| |5~7| 9| 无| |8| 18| a{i}仅由0、9组成| |9~10| 18| a{i}两两相同| |11~12| 18|  无| |13~14|  {10}^{4}| a{i}两两相同| |15~16|  {10}^{4}| a_{i}仅由0、9组成| |17~20| 5\times {10}^{5}$| 无|

2026第五届青少年编程挑战精英赛