Time Limit: 1 s
Memory Limit: 128 MB

Submission：514
AC：297
Score：85.54

Junpei was an ordinary college student
until he found himself kidnapped and confined to a room abroad some kind of
ship. After solving the puzzles keeping him locked in the room, he discovered
that 8 other men and women had also been kidnapped including his childhood
friend, Akane Kurashiki. Suddenly the voice of someone calling themselves Zero
spoke from some speakers overhead:”I mean to have you participate in a game. **The Nonary Game**.”

To win the Nonary Game. They had to pass
through the Numbered Doors located around the ship to find the 9^{th} door.
Three to five participants could scan their bracelets at a door, but their
digital root had to match the number of the door to open it. To find the **digital root**, add up the bracelet numbers, than add the numbers form each
decimal place of the sum until you have a single-digit number. For example, the
digital root of 1 and 2 is 1+2=3, the digital root of 3,5 and 7 is
3+5+7=15=1+5=6.

Your task is to find out the digital roots of the given participants.

The first line is an integer *t*, represents
the input has *t*(t≤100) test cases.

For each test case, there are two lines,
the first contains an integer *n*(3≤n≤5), represents there are *n *participants. The second line contains *n *numbers *a1,a2…an*(0≤ai≤9, 1≤i≤n), represent the bracelet number of each participant.

For each test case, you have to output a
line contains an integer *d *which indicate the digital roots of the
participants.

input

2
2
1 2
3
1 2 3

output

3
6