Problem Statement

You have a number N and you want to calculate how many divisors of N are special.


A number is said to be special if it is possible to remove some digits from it to get a number having 3, 5 or 6 only.For exemple number 38597 is special since it is posible to  remove digits 8, 9, 7 to get 35. You can remove some digits but not all digits. You can remove digits from left, right or middle.


Constraints

1 <= T <= 10
1 <= N <= 10^9

Input

First line of input containes an integer T, number of test cases and then t test cases follow. Each test case is of one line containing an integer N.


Output

Output is of T lines, one for each test case. Each line contains number of special devisiors of respective test case.


Example
Input:

2
15
75
Output

3
5
from math import sqrt
t=input()
while t!=0:
        n=input()
        c=0
        for i in range(2,int(sqrt(n))+1):
                if n%i==0:
                        if str(i).find('5')!=-1 or str(i).find('3')!=-1 or str(i).find('6')!=-1:
                                c+=1
                        #       print i
                        if str(n/i).find('5')!=-1 or str(n/i).find('3')!=-1 or str(n/i).find('6')!=-1:
                                c+=1
                        #       print n/i
 
 
        if str(n).find('3')!=-1 or str(n).find('5')!=-1 or str(n).find('6')!=-1:
                c+=1
        print c
        t-=1