Given a string str consisting of digits, one may group these digits into sub-groups while maintaining their original order.
The task is to count number of groupings such that for every sub-group except the last one, sum of digits in a sub-group is less than or equal to sum of the digits in the sub-group immediately on its right.
For example, a valid grouping of digits of number 1119 is (1-11-9). Sum of digits in first subgroup is 1, next subgroup is 2, and last subgroup is 9. Sum of every subgroup is less than or equal to its immediate right.
 
Example 1: 
Input: str = "1119"
Output: 7
Explanation: [1-119], [1-1-19], [1-11-9], 
[1-1-1-9], [11-19], [111-9] and [1119] 
are seven sub-groups.
Example 2:
Input: str = "12"
Output: 2
Explanation: [1-2] and [12] are two sub-groups.
 
Your Task:
You don't need to read or print anything. Your task is to complete the function TotalCount() which takes the string str as input parameter and returns total possible groupings.
Expected Time Complexity: O(N * N ) where N is length of string.
Expected Space Complexity: O(N * N)
 
Constraints:
1 <= length of string <= 100

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Dynamic programming

Starter code: #User function Template for python3



class Solution:

	def TotalCount(self, s):

		# Code here

Solutions:
from functools import lru_cache

class Solution:

	def TotalCount(self, s):
		n = len(s)
		sums = [[0] * n for _ in range(n)]
		for r in range(n - 1, -1, -1):
			for l in range(r, -1, -1):
				if l == r:
					sums[l][r] = int(s[l])
				else:
					sums[l][r] = int(s[l]) + sums[l + 1][r]

		@lru_cache(None)
		def count(n, start, s):
			if len(s[start:]) == 0:
				return 1
			cnt = 0
			for i in range(start + 1, len(s) + 1):
				nxt_n = sums[start][i - 1]
				if nxt_n >= n:
					cnt += count(nxt_n, i, s)
			return cnt
		return count(0, 0, s)


class Solution:

	def TotalCount(self, s):
		n = len(s)
		summ = 0
		for i in s:
			summ += int(i)
		dp = [[-1 for _ in range(summ + 1)] for _ in range(n + 1)]
		return self.group(n, 0, 0, s, dp)

	def group(self, n, idx, initialsum, s, dp):
		if idx == n:
			return 1
		if dp[idx][initialsum] != -1:
			return dp[idx][initialsum]
		cursum = 0
		ans = 0
		for i in range(idx, n):
			cursum += int(s[i])
			if cursum >= initialsum:
				ans += self.group(n, i + 1, cursum, s, dp)
		dp[idx][initialsum] = ans
		return dp[idx][initialsum]


class Solution:

	def solve(self, s, i, prev, dp):
		n = len(s)
		if i == n:
			return 1
		elif dp[i][prev] != -1:
			return dp[i][prev]
		cur = res = 0
		for j in range(i, n):
			cur += int(s[j])
			if cur >= prev:
				res += self.solve(s, j + 1, cur, dp)
		dp[i][prev] = res
		return dp[i][prev]

	def TotalCount(self, s):
		n = len(s)
		dp = [[-1 for i in range(9 * n)] for j in range(n)]
		return self.solve(s, 0, 0, dp)


def rec(s, i, presum, dp):
	if i == len(s):
		return 1
	elif dp[i][presum] != -1:
		return dp[i][presum]
	cursum = 0
	res = 0
	for j in range(i, len(s)):
		cursum += int(s[j])
		if cursum >= presum:
			res += rec(s, j + 1, cursum, dp)
	dp[i][presum] = res
	return dp[i][presum]

class Solution:

	def TotalCount(self, s):
		dp = [[-1 for i in range(9 * len(s))] for j in range(len(s))]
		return rec(s, 0, 0, dp)


import math

class Solution:

	def gsum(self, s, i, n, last, memo):
		if i == n:
			return 1
		key = (i, last)
		if key in memo:
			return memo[key]
		dsum = 0
		res = 0
		for j in range(i + 1, n + 1):
			dsum += int(s[j - 1])
			if last <= dsum:
				res += self.gsum(s, j, n, dsum, memo)
		memo[key] = res
		return memo[key]

	def TotalCount(self, s):
		n = len(s)
		memo = {}
		res = self.gsum(s, 0, n, -math.inf, memo)
		return res


class Solution:

	def count(self, i, prev_sum, s, n, dp):
		if i == n:
			return 1
		if dp[i][prev_sum] != -1:
			return dp[i][prev_sum]
		ways = 0
		sum = 0
		for j in range(i, n):
			sum += int(s[j])
			if sum >= prev_sum:
				ways += self.count(j + 1, sum, s, n, dp)
		dp[i][prev_sum] = ways
		return dp[i][prev_sum]

	def TotalCount(self, s):
		n = len(s)
		sum = 0
		for digit in s:
			sum += int(digit)
		dp = [[-1 for _ in range(sum + 1)] for _ in range(n)]
		return self.count(0, 0, s, n, dp)


def f(idx, summ, dp, S):
	N = len(S)
	if idx == N:
		return 1
	if dp[idx][summ] != -1:
		return dp[idx][summ]
	dp[idx][summ] = 0
	ans = 0
	tempsumm = 0
	for i in range(idx, N):
		tempsumm += int(S[i])
		if tempsumm >= summ:
			ans += f(i + 1, tempsumm, dp, S)
	dp[idx][summ] = ans
	return ans

class Solution:

	def TotalCount(self, s):
		dp = [[-1 for i in range(901)] for i in range(100)]
		return f(0, 0, dp, s)


class Solution:

	def TotalCount(self, s):
		dp = [[-1 for _ in range(9 * len(s))] for _ in range(len(s) + 1)]

		def sol(str, index, sum):
			if index == len(str):
				return 1
			if dp[index][sum] != -1:
				return dp[index][sum]
			ans = 0
			cursum = 0
			for i in range(index, len(str)):
				cursum += int(str[i])
				if cursum >= sum:
					ans += sol(str, i + 1, cursum)
			dp[index][sum] = ans
			return dp[index][sum]
		return sol(s, 0, 0)


class Solution:

	def TotalCount(self, s):
		n = len(s)
		y = 0
		for i in range(n):
			y += int(s[i])
		dp = []
		for i in range(n + 1):
			x = []
			for j in range(y + 1):
				x.append(-1)
			dp.append(x)

		def solve(i, sm):
			if i == len(s):
				return 1
			if dp[i][sm] != -1:
				return dp[i][sm]
			ans = 0
			temp_sm = 0
			for k in range(i, n):
				temp_sm += int(s[k])
				if temp_sm >= sm:
					ans += solve(k + 1, temp_sm)
			dp[i][sm] = ans
			return ans
		return solve(0, 0)
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		s = input()
		ob = Solution()
		ans = ob.TotalCount(s)
		print(ans)


class Solution:

	def TotalCount(self, s):
		n = len(s)
		summ = 0
		for i in s:
			summ += int(i)
		dp = [[-1 for _ in range(summ + 1)] for _ in range(n + 1)]
		return self.group(n, 0, 0, s, dp)

	def group(self, n, idx, initialsum, s, dp):
		if idx == n:
			return 1
		if dp[idx][initialsum] != -1:
			return dp[idx][initialsum]
		cursum = 0
		ans = 0
		for i in range(idx, n):
			cursum += int(s[i])
			if cursum >= initialsum:
				ans += self.group(n, i + 1, cursum, s, dp)
		dp[idx][initialsum] = ans
		return dp[idx][initialsum]
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		s = input()
		ob = Solution()
		ans = ob.TotalCount(s)
		print(ans)


class Solution:

	def TotalCount(self, s):
		dp = [[-1] * len(s) for _ in range(1000)]

		def rec(i, su):
			if i >= len(s):
				return 1
			if dp[su][i] != -1:
				return dp[su][i]
			sum = 0
			c = 0
			for j in range(i, len(s)):
				sum += int(s[j])
				if sum >= su:
					c += rec(j + 1, sum)
			dp[su][i] = c
			return c
		return rec(0, 0)
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		s = input()
		ob = Solution()
		ans = ob.TotalCount(s)
		print(ans)


class Solution:

	def dfs(self, s, index, prevSum):
		if index >= len(s):
			return 1
		if (index, prevSum) in self.memo:
			return self.memo[index, prevSum]
		currentSum = ans = 0
		for i in range(index, len(s)):
			currentSum += int(s[i])
			if currentSum >= prevSum:
				ans += self.dfs(s, i + 1, currentSum)
		self.memo[index, prevSum] = ans
		return ans

	def TotalCount(self, s):
		self.memo = {}
		return self.dfs(s, 0, -1)


class Solution:

	def dfs(self, s, index, prev):
		if index >= len(s):
			return 1
		if (index, prev) in self.memo:
			return self.memo[index, prev]
		res = 0
		ans = 0
		for i in range(index, len(s)):
			res += int(s[i])
			if res >= prev:
				ans += self.dfs(s, i + 1, res)
		self.memo[index, prev] = ans
		return ans

	def TotalCount(self, s):
		self.memo = {}
		return self.dfs(s, 0, -1)


class Solution:

	def TotalCount(self, s):
		n = len(s)
		maxl = 100
		dp = [[-1 for i in range(9 * maxl + 1)] for i in range(maxl)]

		def helper(p, psum):
			if p == n:
				return 1
			if dp[p][psum] != -1:
				return dp[p][psum]
			ans = 0
			sumd = 0
			dp[p][psum] = 0
			for i in range(p, n):
				sumd += int(s[i])
				if sumd >= psum:
					ans += helper(i + 1, sumd)
			dp[p][psum] = ans
			return dp[p][psum]
		return helper(0, 0)


class Solution:

	def sumi(self, s):
		i = 0
		if s != '':
			for c in s:
				i += int(c)
		return i

	def solve(self, i, j, s, c):
		if i >= j:
			return 0
		for k in range(i, j):
			left = self.solve(i, k, s, c)
			sl = self.sumi(left)
			right = self.solve(k + 1, j, s, c)
			sr = self.sumi(right)
			if sl <= sr:
				c.append(1)
		return c

	def TotalCount(self, s):
		n = len(s)
		maxl = 100
		dp = [[-1 for i in range(9 * maxl + 1)] for i in range(maxl)]

		def helper(p, psum):
			if p == n:
				return 1
			if dp[p][psum] != -1:
				return dp[p][psum]
			ans = 0
			sumd = 0
			dp[p][psum] = 0
			for i in range(p, n):
				sumd += int(s[i])
				if sumd >= psum:
					ans += helper(i + 1, sumd)
			dp[p][psum] = ans
			return dp[p][psum]
		return helper(0, 0)


class Solution:

	def TotalCount(self, s):
		n = len(s)
		memo = {}

		def util(pos, prev):
			if pos >= n:
				return 1
			if (pos, prev) in memo:
				return memo[pos, prev]
			curr = 0
			vals = 0
			for i in range(pos, n):
				curr += int(s[i])
				if curr >= prev:
					vals += util(i + 1, curr)
			memo[pos, prev] = vals
			return vals
		return util(0, -100000000.0)


class Solution:

	def group(self, s, index, count, d):
		if index == len(s):
			return 1
		ans = 0
		currentSum = 0
		if d[index][count] != -1:
			return d[index][count]
		for i in range(index, len(s)):
			currentSum += int(s[i])
			if currentSum >= count:
				ans += self.group(s, i + 1, currentSum, d)
		d[index][count] = ans
		return ans

	def TotalCount(self, s):
		d = [[-1 for i in range(9 * len(s))] for j in range(len(s))]
		return self.group(s, 0, 0, d)


class Solution:

	def TotalCount(self, s):
		n = len(s)
		dp = [[-1] * (9 * n + 1) for _ in range(100)]

		def helper(gs, psum):
			if gs == n:
				return 1
			if dp[gs][psum] != -1:
				return dp[gs][psum]
			csum = 0
			ans = 0
			for i in range(gs, n):
				csum += int(s[i])
				if csum >= psum:
					ans += helper(i + 1, csum)
			dp[gs][psum] = ans
			return dp[gs][psum]
		return helper(0, 0)


class Solution:

	def TotalCount(self, s):
		n = len(s)
		su = 0
		for i in s:
			su += int(i)
		dp = [[-1 for _ in range(su + 1)] for _ in range(n + 1)]
		return self.group(n, 0, 0, s, dp)

	def group(self, n, ind, su, s, dp):
		if ind == n:
			return 1
		if dp[ind][su] != -1:
			return dp[ind][su]
		cursum = 0
		ans = 0
		for i in range(ind, n):
			cursum += int(s[i])
			if cursum >= su:
				ans += self.group(n, i + 1, cursum, s, dp)
		dp[ind][su] = ans
		return dp[ind][su]


class Solution:

	def TotalCount(self, s):
		sum2 = 0
		n = len(s)
		for i in s:
			sum2 += int(i)
		dp = [[-1 for i in range(sum2 + 1)] for i in range(n + 1)]
		return self.group(n, 0, 0, s, dp)

	def group(self, n, index, sum1, s, dp):
		if index == n:
			return 1
		if dp[index][sum1] != -1:
			return dp[index][sum1]
		curr_sum = 0
		ans = 0
		for i in range(index, n):
			curr_sum += int(s[i])
			if curr_sum >= sum1:
				ans += self.group(n, i + 1, curr_sum, s, dp)
		dp[index][sum1] = ans
		return dp[index][sum1]


class Solution:

	def TotalCount(self, num):
		dp = {}

		def count_parts(pre_sum, num_lis):
			if not num_lis:
				return 1
			if (num_lis, pre_sum) in dp:
				return dp[num_lis, pre_sum]
			cur_sum = 0
			count = 0
			for i in range(len(num_lis)):
				cur_sum += num_lis[i]
				if cur_sum >= pre_sum:
					count += count_parts(cur_sum, num_lis[i + 1:])
			dp[num_lis, pre_sum] = count
			return count
		num_lis = [int(i) for i in str(num)]
		return count_parts(0, tuple(num_lis))


class Solution:

	def TotalCount(self, s):
		n = len(s)
		summ = 0
		for i in s:
			summ += int(i)
		dp = [[-1 for i in range(summ + 1)] for j in range(n + 1)]
		return self.group(n, 0, 0, s, dp)

	def group(self, n, index, sum1, s, dp):
		if index == n:
			return 1
		if dp[index][sum1] != -1:
			return dp[index][sum1]
		currsum = 0
		ans = 0
		for i in range(index, n):
			currsum += int(s[i])
			if currsum >= sum1:
				ans += self.group(n, i + 1, currsum, s, dp)
		dp[index][sum1] = ans
		return dp[index][sum1]


from functools import lru_cache

class Solution:

	def TotalCount(self, s):

		@lru_cache(maxsize=None)
		def cal(i, summ):
			if i == len(s):
				return 1
			ans = 0
			csum = 0
			for k in range(i, len(s)):
				csum += int(s[k])
				if csum >= summ:
					ans += cal(k + 1, csum)
			return ans
		return cal(0, 0)


class Solution:

	def solve(self, dp, s, n, Sum, idx):
		if idx >= n:
			return 1
		if dp[idx][Sum] != -1:
			return dp[idx][Sum]
		currSum = 0
		res = 0
		for i in range(idx, n):
			currSum += int(s[i])
			if currSum >= Sum:
				res += self.solve(dp, s, n, currSum, i + 1)
		dp[idx][Sum] = res
		return res

	def TotalCount(self, s):
		Sum = 0
		for i in range(len(s)):
			Sum += int(s[i])
		dp = [[-1 for _ in range(Sum + 1)] for _ in range(len(s) + 1)]
		return self.solve(dp, s, len(s), 0, 0)


class Solution:

	def recur(self, p, prev_sum, s, dp):
		if p >= len(s):
			return 1
		if dp[p][prev_sum] != -1:
			return dp[p][prev_sum]
		ans = sm = 0
		for i in range(p, len(s)):
			sm += int(s[i])
			if sm >= prev_sum:
				ans += self.recur(i + 1, sm, s, dp)
		dp[p][prev_sum] = ans
		return ans

	def TotalCount(self, s):
		n = 1
		for i in s:
			n += int(i)
		dp = [[-1 for i in range(n)] for i in range(len(s))]
		return self.recur(0, 0, s, dp)


class Solution:

	def util(self, n, ind, ism, s, dp):
		if ind == n:
			return 1
		if dp[ind][ism] != -1:
			return dp[ind][ism]
		(res, cs) = (0, 0)
		for i in range(ind, n):
			cs += int(s[i])
			if cs >= ism:
				res += self.util(n, i + 1, cs, s, dp)
		dp[ind][ism] = res
		return dp[ind][ism]

	def TotalCount(self, s):
		(n, sm) = (len(s), 0)
		for i in s:
			sm += int(i)
		dp = [[-1 for _ in range(sm + 1)] for _ in range(n + 1)]
		return self.util(n, 0, 0, s, dp)


class Solution:

	def countSubgroups(self, n, position, num, previous_sum, dp):
		if position == n:
			return 1
		if dp[position][previous_sum] != -1:
			return dp[position][previous_sum]
		dp[position][previous_sum] = 0
		s = 0
		res = 0
		for i in range(position, n):
			s += int(num[i])
			if s >= previous_sum:
				res += self.countSubgroups(n, i + 1, num, s, dp)
		dp[position][previous_sum] = res
		return res

	def TotalCount(self, s):
		n = len(s)
		dp = [[-1 for i in range(n * 9)] for j in range(n)]
		ans = self.countSubgroups(n, 0, s, 0, dp)
		return ans


class Solution:

	def TotalCount(self, s):
		dp = {}

		def countGroup(position, pre_sum, length, s):
			if position == length:
				return 1
			if (position, pre_sum) in dp:
				return dp[position, pre_sum]
			res = 0
			sum = 0
			for i in range(position, length):
				sum += int(s[i])
				if sum >= pre_sum:
					res = res + countGroup(i + 1, sum, length, s)
			dp[position, pre_sum] = res
			return dp[position, pre_sum]
		return countGroup(0, 0, len(s), s)


class Solution:

	def TotalCount(self, s):

		def task(n, i, ism, s, dp):
			if i == n:
				return 1
			if dp[i][ism] != -1:
				return dp[i][ism]
			cm = 0
			ans = 0
			for j in range(i, n):
				cm += int(s[j])
				if cm >= ism:
					ans += task(n, j + 1, cm, s, dp)
			dp[i][ism] = ans
			return dp[i][ism]
		n = len(s)
		sm = 0
		for i in s:
			sm += int(i)
		dp = [[-1 for _ in range(sm + 1)] for _ in range(n + 1)]
		return task(n, 0, 0, s, dp)


[7, -1, -1, -1]
[-1, 4, -1, -1]
[-1, 2, 1, -1]
[-1, 1, 1, 1]

class Solution:

	def TotalCount(self, s):

		def haha(ind, sumi, s, dp, n):
			if ind == n:
				return 1
			if dp[ind][sumi] != -1:
				return dp[ind][sumi]
			(c, ans) = (0, 0)
			for i in range(ind, n):
				c += int(s[i])
				if c >= sumi:
					ans = ans + haha(i + 1, c, s, dp, n)
			dp[ind][sumi] = ans
			return dp[ind][sumi]
		n = len(s)
		dp = [[-1] * (n * 9) for i in range(n)]
		x = haha(0, 0, s, dp, n)
		return x


class Solution:

	def Grouping(self, s, idx, sum, dp):
		if idx == len(s):
			return 1
		if dp[idx][sum] != -1:
			return dp[idx][sum]
		currentSum = 0
		ans = 0
		i = idx
		while i < len(s):
			currentSum += int(s[i])
			if currentSum >= sum:
				ans += self.Grouping(s, i + 1, currentSum, dp)
			i += 1
		dp[idx][sum] = ans
		return ans

	def TotalCount(self, s):
		n = len(s)
		summ = 0
		for i in s:
			summ += int(i)
		dp = [[-1 for x in range(summ + 1)] for x in range(n + 1)]
		return self.Grouping(s, 0, 0, dp)


class Solution:

	def TotalCount(self, s):
		n = len(s)
		dp = [[-1 for j in range(9 * n)] for i in range(n)]
		return self.groupings(s, 0, 0, dp)

	def groupings(self, str, idx, sum, dp):
		if idx == len(str):
			return 1
		if dp[idx][sum] != -1:
			return dp[idx][sum]
		cSum = 0
		ans = 0
		for i in range(idx, len(str)):
			cSum += int(str[i])
			if cSum >= sum:
				ans += self.groupings(str, i + 1, cSum, dp)
		dp[idx][sum] = ans
		return dp[idx][sum]


class Solution:

	def TotalCount(self, a):
		s = 0
		for i in a:
			s += int(i)
		dp = [[-1 for _ in range(s + 1)] for _ in range(len(a))]

		def rec(st, ls, n):
			if st == n:
				return 1
			if dp[st][ls] != -1:
				return dp[st][ls]
			s = 0
			curr = 0
			for i in range(st, n):
				s += int(a[i])
				if s >= ls:
					curr += rec(i + 1, s, n)
			dp[st][ls] = curr
			return curr
		return rec(0, 0, len(a))


class Solution:

	def TotalCount(self, s):
		n = len(s)
		sums = 0
		for i in s:
			sums += int(i)
		dp = [[-1 for _ in range(sums + 1)] for _ in range(n)]

		def fun(i, pre):
			nonlocal n
			if i == n:
				return 1
			if dp[i][pre] != -1:
				return dp[i][pre]
			ans = 0
			sumi = 0
			for j in range(i, n):
				sumi += int(s[j])
				if sumi >= pre:
					ans += fun(j + 1, sumi)
			dp[i][pre] = ans
			return ans
		return fun(0, 0)


class Solution:

	def TotalCount(self, s):
		n = len(s)
		sums = 0
		for i in s:
			sums += int(i)
		dp = [[-1 for _ in range(sums + 1)] for _ in range(n)]

		def fun(i, pre):
			nonlocal n
			if i == n:
				return 1
			if dp[i][pre] != -1:
				return dp[i][pre]
			ans = 0
			sumi = 0
			for j in range(i, n):
				sumi += int(s[j])
				if sumi >= pre:
					ans += fun(j + 1, sumi)
			dp[i][pre] = ans
			return ans
		return fun(0, 0)
		n = len(s)
		summ = 0
		for i in s:
			summ += int(i)
		dp = [[-1 for _ in range(summ + 1)] for _ in range(n + 1)]
		return self.group(n, 0, 0, s, dp)

	def group(self, n, idx, initialsum, s, dp):
		if idx == n:
			return 1
		if dp[idx][initialsum] != -1:
			return dp[idx][initialsum]
		cursum = 0
		ans = 0
		for i in range(idx, n):
			cursum += int(s[i])
			if cursum >= initialsum:
				ans += self.group(n, i + 1, cursum, s, dp)
		dp[idx][initialsum] = ans
		return dp[idx][initialsum]


class Solution:

	def TotalCount(self, s):

		def helper(i, s):
			if dp[i][s] == -1:
				cs = 0
				res = 0
				for j in range(i, n):
					cs += l[j]
					if cs >= s:
						res += helper(j + 1, cs)
				dp[i][s] = res
			return dp[i][s]
		l = [int(i) for i in s]
		n = len(s)
		strsum = sum(l)
		dp = [[-1 for j in range(strsum + 1)] for i in range(n + 1)]
		for i in range(strsum + 1):
			dp[n][i] = 1
		return helper(0, 0)


from collections import defaultdict

class Solution:

	def TotalCount(self, s):
		dp = [[-1] * (len(s) * 9) for i in range(len(s))]

		def countGroups(position, previous_sum, length, num):
			if position == length:
				return 1
			if dp[position][previous_sum] != -1:
				return dp[position][previous_sum]
			res = 0
			sum = 0
			for i in range(position, length):
				sum += int(s[i])
				if sum >= previous_sum:
					res += countGroups(i + 1, sum, length, num)
			dp[position][previous_sum] = res
			return res
		return countGroups(0, 0, len(s), s)


class Solution:

	def TotalCount(self, s):
		dp = {}
		n = len(s)

		def helper(ind, sum):
			if ind == n:
				return 1
			if (ind, sum) in dp:
				return dp[ind, sum]
			curr_sum = 0
			ans = 0
			for i in range(ind, n):
				curr_sum += ord(s[i]) - ord('0')
				if curr_sum >= sum:
					ans += helper(i + 1, curr_sum)
			dp[ind, sum] = ans
			return dp[ind, sum]
		return helper(0, 0)


class Solution:

	def TotalCount(self, s):
		n = len(s)
		dp = [[-1 for i in range(9 * n)] for j in range(n)]
		return self.solve(s, 0, 0, dp)

	def solve(self, S, index, sum_, dp):
		if index == len(S):
			return 1
		if dp[index][sum_] != -1:
			return dp[index][sum_]
		currsum = 0
		ans = 0
		for i in range(index, len(S)):
			currsum += int(S[i])
			if currsum >= sum_:
				ans += self.solve(S, i + 1, currsum, dp)
		dp[index][sum_] = ans
		return ans


from collections import defaultdict

class Solution:

	def countGreater(self, array, dp_table, j, m):
		if len(array) == j:
			return 1
		if dp_table[j][m] != -1:
			return dp_table[j][m]
		r = 0
		k = 0
		for i in range(j, len(array)):
			e = array[i]
			k += e
			if k < m:
				continue
			r += self.countGreater(array, dp_table, i + 1, k)
		dp_table[j][m] = r
		return r

	def TotalCount(self, s):
		dp_table = list((defaultdict(lambda : -1) for i in range(len(s))))
		array = []
		cumsum = []
		r = 0
		for i in range(len(s)):
			r += int(s[i])
			cumsum.append(r)
			array.append(int(s[i]))
		return self.countGreater(array, dp_table, 0, 0)


class Solution:

	def TotalCount(self, s):
		arr = [int(ch) for ch in s]
		(n, tot) = (len(s), sum(arr))
		dp = [[-1] * (tot + 1) for _ in range(n)]
		return self.find_count(arr, 0, len(s), 0, dp)

	def find_count(self, arr, i, n, prev, dp):
		if i == n:
			return 1
		elif dp[i][prev] >= 0:
			return dp[i][prev]
		cnt = sm = 0
		for ind in range(i, n):
			sm += arr[ind]
			if sm >= prev:
				cnt += self.find_count(arr, ind + 1, n, sm, dp)
		dp[i][prev] = cnt
		return cnt


class Solution:

	def isValidGroupping(self, s, idx, dp, prev_sum):
		if idx == len(s):
			return 1
		if dp[idx][prev_sum] != -1:
			return dp[idx][prev_sum]
		curr_sum = 0
		ans = 0
		for i in range(idx, len(s)):
			curr_sum += int(s[i])
			if curr_sum >= prev_sum:
				ans += self.isValidGroupping(s, i + 1, dp, curr_sum)
		dp[idx][prev_sum] = ans
		return ans

	def TotalCount(self, s):
		s_len = len(s)
		dp = [[-1 for i in range(s_len * 9 + 1)] for i in range(s_len)]
		return self.isValidGroupping(s, 0, dp, 0)


class Solution:

	def TotalCount(self, s):

		def is_possible(i, prev, dp):
			if i == n:
				return 1
			if dp[i][prev] != -1:
				return dp[i][prev]
			res = 0
			for j in range(i, n):
				summ = pre_sum[j + 1] - pre_sum[i]
				if summ >= prev:
					res += is_possible(j + 1, summ, dp)
			dp[i][prev] = res
			return res
		n = len(s)
		pre_sum = [0]
		for i in range(n):
			pre_sum.append(pre_sum[-1] + int(s[i]))
		dp = [[-1] * 1000 for _ in range(n)]
		return is_possible(0, int(s[0]), dp)


class Solution:

	def TotalCount(self, s):
		dp = [[-1 for _ in range(9 * len(s) + 1)] for _ in range(len(s))]

		def rec(i, sm):
			if i == len(s):
				return 1
			if dp[i][sm] != -1:
				return dp[i][sm]
			dp[i][sm] = 0
			sum_ = 0
			for j in range(i, len(s)):
				sum_ += int(s[j])
				if sum_ >= sm:
					dp[i][sm] += rec(j + 1, sum_)
			return dp[i][sm]
		return rec(0, 0)