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.