NITT5 - Subset and upset

The whole world is crazy about subset sum. We define subset sum as sum of all subparts. A subpart is a number which is obtained by erasing certain digits and arranging the remaining numbers in the same order. You have to calculate the subset sum of the given number. Since the number can be very large return the subset sum modulo 9.

For example if the number is 1357, then the various subparts are 1, 3, 5, 7, 13, 15, 17, 35, 37, 57, 137, 135, 157, 357, 1357.

Input

First line contains T denoting the number of test cases (T <= 50).

Next T lines containing the number (maximum number digits of the number can be 51).

Output

Print the subset sum modulo 9

Example

Input:
2
456
111

Output:
6
3

Added by:jack(chakradarraju)
Date:2012-09-23
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

hide comments
2015-05-31 15:50:39 Rishabh Joshi
Loved solving it in O(n).
Such a sweet solution. Amazing problem.
Try to do it in O(n).
2012-10-03 14:27:13 (Tjandra Satria Gunawan)(曾毅昆)
@zukow: Yes, thanks for the idea, I've made the problem SUBSHARD
@Francky: It's not "exactly" same task but just "similar" task.
2012-10-02 22:57:23 :D
This could be a good problem if modulo was a parameter in test case (<=10^9), and digits number <= 1000.
2012-10-02 20:15:38 Francky
Should be move to tutorial.
POWERSUM is better with mod 10**9+7, and exactly same task.
2012-10-02 12:02:20 (Tjandra Satria Gunawan)(曾毅昆)
mod 9 make this problem easy...
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.