P20493 [HackerEarth] 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.
普及
题目描述

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.

SAMPLE INPUT
1
9876

SAMPLE 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.

输入格式

见题面

输出格式

见题面

样例输入
70 283181851808648911928482704892585327484355012361532 204658345634140012788287232924387932430359554786873 295642045682933909398116941224455878721500122865012 297214013775877369516166116034861568896050185964956 277568912496769650564378069722402726340011864716538 224255996445851546419236976411839492501859708504621 289738472135061965992621208291935538335338484317229 280841358199532731788675578852237115816321830910341 241416257545946283658535175089566628181421932520933 240133607264372947472434698570165525891382143467826 238113906584017765634201423787114463941819919769779 249473547672939481521389604001811287579261514466417 245093787950853130821138670588482647734109837212073 252396608384165384885371440671729431167794128705953 229242581726863491007504247232770389326256601594736 266957643924272380623283551652010264236522898635959 251912796399122612107163764057678456514539672709966 266200617810065093128949136659485188485523577031638 239369303709527759563357796240297207506522356645461 260687171075117384910559658853390803669960484231262 291091819393005212680449832327552393283563884132546 204819900998207186463219311285864179000686585176302 277504349729453425278308627888606146166437683669051 241671622083622185426202897774417510486683516157785 264934780979624544036683744661374422999607533175631 281089615435157995332152366504531860552473034384468 235101142971131277374068204539922532388413011895898 298242108085148966323176394864864237113709130727606 240294062653913778389501425899019323838242845303778 267250237754436419747971460220376568787708366427271 273175136347973442972680133047875758108742293128047 228521898162324145950443784631661333130018202580081 285545441238984425506589699199735895722930924830861 293245210202999777046112186127584723367581169877070 213718300115126520740542396393225540972092758335650 283838254073076400951284810026922853567679582282032 298723837287023453640206363444015303492630962934307 248813146840188450819811607960497886099794865985271 253347942607262892693575308690217525823694928534882 273500693470791693009190512898224902690591820257250 205604549812070345452021833280915002309359647339637 290268664760885105063867366066154085466306395474109 282803135014163472441107256554229687301225481442842 236250639410471599743307228225097734378503137465352 239919144501964619013838934190898580739999992532851 296540156533004505291515937767633663117453358608817 200081260662319867117022544974732926735707913214338 231279536155777436723977397717988772226878003074522 234771969545480390377117719175563045162207757798238 211705869005299560482635240330689466167522372388939 287064944347091839724970357071141622979437696099314 276654548202114438269770449340386923894186728700150 281991399122920107487853980260814387593521306877815 232314401649080612350643786690057341831321232741864 257003758820026136142644925656563249348418739458869 213556309925331097543906486184756348687147953891850 210902535882354916663490987231983259577650611806017 231542318571629307873319816948493804003197457985567 247034818661729561320965697736457414221215496545583 244338757651229398862468667649671498172546895872273 294049270070298959751292548229505253650948887689913 263271810268440173926919497414938653690639553687539 282389893503890863529962009377000507498537726021042 224888001774045767750591837230147819196714453860973 271741058756271629567831663947956468094672832460345 286854982434698785454038508355097768609881419058374 292643763603932489370162743854967256202736520579578 270213732140137872703662765629657449930704492916024 288216362066857869404219460487337781315382749570350 220206789356995006537415410231805699869945934875881
样例输出
12507 18293 11638 4040 16601 16029 9717 8702 19358 10109 15622 14754 10475 9592 24665 20495 11838 12850 12801 12682 14444 45763 13955 13964 10620 9320 6889 12397 13096 18370 5340 6147 18571 12042 16946 14571 32550 12564 15502 12054 14125 7763 9286 19340 12780 9465 9443 7034 12697 7753 10607 8730 5552 29926 11701 8833 17401 12139 16924 17966 29222 8703 11550 5582 13639 19050 7944 19843 9675 19895