11258 - String Partition

John是一位ACM程式題目的出題者，他這次想出一題超簡單的題目，給定一列非負整數，請將所有數值相加。

但是他在產生輸入資料時犯了一個錯誤，就是忘了在一列整數之間輸出用來分隔的空白字元，這導致所有數值都連在一起變成一列字串。

最後他將問題改成：請將該字串分割成數個以非零開頭的32位元有號整數(但可包含0)，請找出使所有數字的總和最大的分割方式，並輸出其總和。

Input
輸入資料的第一列有一個整數N(<= 500)表示測試資料的組數，每組資料一列包含最多200個位數的數字。

Output
請依題意輸出最大的數字總和。

Sample input

6
1234554321
5432112345
000
121212121212
2147483648
11111111111111111111111111111111111111111111111111111

Sample output

1234554321
543211239
0
2121212124
214748372
5555555666

---

原文出處