Given a number S(in the form of a string). Count all the digits in S which divide S. Divisibility by 0 is not allowed. If any digit in S which is repeated divides S, then all repetitions of that digit should be counted.
Example 1:
Input:
S = "35"
Output:
1
Explanation:
Only 5 digits 35,thus the answer is 1.
Example 2:
Input:
S = "1122324"
Output:
7
Explanation:
All the digits divide 1122324, therefore,
the answer is 7.
Your Task:
You don't need to read input or print anything.Your task is to complete the function divisibleByDigits()  which takes the number S(in the form of a string) as input parameter and returns the number of digits of S that divide S.
Expected Time Complexity: O(N)
Expected Auxillary Space: O(constant)
Constraints:
1<=|S|<=10^{6}

Source: geeksforgeeks | Difficulty: EASY
Tags: Mathematics

Starter code: #User function Template for python3



class Solution:    

    def divisibleByDigits(self,S):

        #code here

Solutions:
class Solution:

	def divisibleByDigits(self, S):
		c = 0
		d = {}
		a = int(S)
		s = set()
		for i in S:
			if i not in d:
				d[i] = 0
				if i != '0' and a % int(i) == 0:
					s.add(i)
			d[i] += 1
		for i in s:
			c += d[i]
		return c


class Solution:

	def divisibleByDigits(self, S):
		d = {}
		ans = 0
		x = int(S)
		for i in range(1, 10):
			if x % i == 0:
				d[str(i)] = 1
			else:
				d[str(i)] = 0
		for i in S:
			if i == '0':
				pass
			else:
				ans += d[i]
		return ans


class Solution:

	def divisibleByDigits(self, S):
		d = {}
		ans = 0
		x = int(S)
		for i in S:
			if i == '0':
				pass
			else:
				i = int(i)
				if i in d:
					if d[i] == True:
						ans += 1
				elif x % i == 0:
					ans += 1
					d[i] = True
				else:
					d[i] = False
		return ans


class Solution:

	def divisibleByDigits(self, S):
		ans = 0
		arr = list([0, 0, 0, 0, 0, 0, 0, 0, 0, 0])
		s = set()
		for i in S:
			arr[int(i)] = arr[int(i)] + 1
			s.add(int(i))
		S = int(S)
		for i in s:
			if i == 0:
				pass
			elif S % i == 0:
				ans += arr[i]
		return ans


class Solution:

	def divisibleByDigits(self, S):
		d = int(S)
		c = 0
		s = {}
		for i in S:
			if i in s:
				s[i] += 1
			else:
				s[i] = 1
		for i in s:
			if i != '0':
				if d % int(i) == 0:
					c += s[i]
		return c


class Solution:

	def divisibleByDigits(self, S):
		c = 0
		d = {}
		a = int(S)
		s = set()
		for i in S:
			if i not in d:
				d[i] = 0
				if i != '0' and a % int(i) == 0:
					s.add(i)
			d[i] += 1
		for i in s:
			c += d[i]
		return c
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		S = input()
		ob = Solution()
		print(ob.divisibleByDigits(S))