Special Sum of Array

You have been given an array/list ‘arr’ of length ‘N’, which contains single digit elements at every index. Your task is to return the sum of all elements of the array. But the final sum should also be a single digit.

To keep the output single digit - you need to keep adding the digits of the output number till a single digit is left.

For example:

For the given array [5, 8, 4, 9]

The sum of the elements of the array will be
5 + 8 + 4 + 9 = 26.
Since 26 is not a single-digit number, we will again take the sum of the digits of 26. 
2 + 6 = 8.
Now 8 is a single-digit number. So we will stop here and return 8.

Input Format:

The first line contains a single integer ‘T’ denoting the number of test cases to be run. Then the test cases follow.

The first line of each test case contains a single integer ‘N’, representing the size of the array.

The second line of each test case contains ‘N’ space-separated integers representing the elements of the given array.

Output Format:

For each test case, print a single-digit integer representing the sum of the array.

Output for each test case will be printed in a separate line.

Note

You are not required to print anything, it has already been taken care of. Just implement the function.

Constraints:

1 <= T <= 100
1 <= N <= 10^3
0 <= arr[i] <= 9

It is guaranteed that the sum of ‘N’ over all test cases doesn’t exceed 10^5.

Time Limit: 1 sec.

Sample Input 1:

2
5
8 7 0 1 2
4
4 2 1 1

Sample Output 1:

9
8

Explanation For Sample Output 1:

Test Case 1:

For the given array [8, 7, 0, 1, 2]
The sum of the elements of the array will be
8 + 7 + 0 + 1 + 2 = 18.

Since 18 is not a single-digit number, we will again take the sum of the digits of 18. 
1 + 8 = 9.
Now 9 is a single-digit number. So we will stop here and return 9.

Test Case 2:

For the given array [4, 2, 1, 1]
The sum of the elements of the array will be
4 + 2+ 1 + 1 = 8.
Since 8 is a single-digit number, we will just return 8.

Sample Input 2:

2
4
3 1 2 1
9
1 9 4 6 2 8 2 0 1

Sample Output 2:

7
6