# SGU 118 - Digital Root

## Description

Let $f(n)$ be a sum of digits for positive integer $n$. If $f(n)$ is one-digit number then it is a digital root for $n$ and otherwise digital root of $n$ is equal to digital root of $f(n)$. For example, digital root of 987 is 6. Your task is to find digital root for expression $$A_1\cdot A_2\cdots A_N + A_1\cdot A_2\cdots A_{N-1} + \cdots + A_1\cdot A_2 + A_1$$

## Input

Input file consists of few test cases. There is $K$ ($1\leq K\leq 5$) in the first line of input.

Each test case is a line. Positive integer number $N$ is written on the first place of test case ($N\leq 1000$). After it there are $N$ positive integer numbers (sequence $A$). Each of this numbers is non-negative and not more than $10^9$.

## Output

Write one line for every test case. On each line write digital root for given expression.

## Sample Input

 1 2  1 3 2 3 4 

## Sample Output

 1  5 

## Solution

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32  #include using namespace std; const int MAX = 1024; int pData[MAX]; int main() { int T, N; cin >> T; for(int i = 1; i <= T; i++) { int ans = 0; cin >> N; for(int j = 1; j <= N; j++) { cin >> pData[j]; pData[j] %= 9; } for(int j = 1; j <= N; j++) { int nTmp = 1; for(int k = 1; k <= j; k++) { nTmp *= pData[k]; if(nTmp >= 9) { nTmp %= 9; } } ans += nTmp; if(ans >= 9) { ans %= 9; } } cout << (ans == 0 ? 9 : ans) << endl; } }