The campus is abuzz with synapse fever and the synapse committee is planning a new game this year.The rules are simple enough and you have to outsmart other players to win it. You will be given a string containing only digits between 1 and 9(both inclusive). You can divide the string in segments such that for every segment formed,the sum of digits in that segment should be less than or equal to the sum of digits in the segment to the right of it. You may not divide the string and thus keep only one segment.There is no constraint on the number of divisions. Your task is to give the total number of possibilities of such divisions or segments from the given string.

Input

First line will contain single integer 1<=n<=70 denoting number of test cases. For every test case a single string of length 1<=l<=50.

Output

For every test case output single integer denoting total number of possibilities of divisions or segments from the given string.

Sample:

Input

1

9876

Output

2

Explanation: There are only two possible outcomes (i)No division so the segment is 9876 (ii)One division after 9,so segments are 9 and 876,where (9)<=(8+7+6). Thus ans is 2.