HZNUOJ

Zero Escape - 9 hours 9 persons 9 doors: Digital Root

Tags:
Time Limit:  1 s      Memory Limit:   128 MB
Submission:522     AC:299     Score:85.54

Description

    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 9th 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.


Input

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(t100) test cases.

For each test case, there are two lines, the first contains an integer n(3n5), represents there are n participants. The second line contains n numbers a1,a2…an(0ai9, 1in), represent the bracelet number of each participant.

Output

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

Samples

input
2 2 1 2 3 1 2 3
output
3 6

Author

ZHANG, Shen