Quan_Lank is a great team with some uncommon interests in programming. Sometimes the team loves to solve strings puzzles, sometimes game puzzles and sometimes metrix type puzzles . Yesterday they have added a new interest to their list that is 'number theory' as they have solved some amazing puzzles related to number theory in the school programming contest held yesterday . Out of all the puzzles they got yesterday, one puzzle is still unsolvable . Actualy they are not getting any clue this time. Quan_Lank is a great team in the history of programming but still the team needs your help . so have a look on the puzzle and help the team Quan_Lank .

Puzzle -

Given a positive integer x . You have to find the no. of positive integers d, such that d is the divisor of x, and x and d have at least one common (the same) digit in their decimal representations.
help the team to find the described number.

INPUT :

First line of Input contains no. of test cases T(T ≤ 100).
Each test case contains one line having a single integer x (1 ≤ x ≤ 10^9).

OUTPUT :

For each test case print a single integer - the answer to the problem.

SAMPLE INPUT
2
1
10

SAMPLE OUTPUT
1
2
t = int(raw_input())

def check(k,dict):
	kk = str(k)
	for char in kk:
		if (dict.has_key(char) == True):
			return True;
	return False;

while (t>0):
	i = int(raw_input())
	j = str(i)
	dict = {}
	for char in j:
		dict[char] = 1
	k = 1;
	count = 0;
	while (k*k <= i):
		if (i % k == 0):
			if (check(k,dict) == True):
				count += 1;
			if (i/k != k and check(i/k,dict) == True):
				count += 1
		k += 1
	print count;
	t -= 1