Problem Statement

Maxim likes dividers of the numbers. Also Maxim is fond of lucky numbers of small elephant from Lviv city.
 
If you remember, lucky numbers are positive integers whose decimal representation contains only the lucky digits 4 and 7. For example, numbers 47, 744, 4 are lucky, 5, 17, 467 — aren't.
 
Now Maxim is interested in the next information: what is the number of the integer positive dividers of number n, which are overlucky.
 
We call number overlucky if it is possible to remove some, but not all, digits and during bonding the remaining digits we will receive a lucky number. For example, number 72344 — overlucky, because it is possible to remove digits 2 and 3, and get number 744, which is lucky. Number 223 isn't overlucky.

 

Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows. Single line of each test case contains an integer n.
 

Output
For each test case on different lines print the answer to the problem.

Constraints

1 ≤ T ≤ 10
1 ≤ n ≤ 10^9

 

Example
Input:
10
1
2
3
4
5
6
7
8
9
10

Output:
0
0
0
1
0
0
1
1
0
0
'''
Maxim and Dividers

Problem code: MAANDI

Problem Statement

Maxim likes dividers of the numbers. Also Maxim is fond of lucky 
numbers of small elephant from Lviv city.

If you remember, lucky numbers are positive integers whose decimal 
representation contains only the lucky digits 4 and 7. For example, 
numbers 47, 744, 4 are lucky, 5, 17, 467 - aren't.

Now Maxim is interested in the next information: what is the number of
the integer positive dividers of number n, which are overlucky.

We call number overlucky if it is possible to remove some, but not 
all, digits and during bonding the remaining digits we will receive a
lucky number. For example, number 72344 - overlucky, because it is
possible to remove digits 2 and 3, and get number 744, which is lucky.
Number 223 isn't overlucky.

Input

The first line of the input contains an integer T denoting the number
of test cases. The description of T test cases follows. Single line 
of each test case contains an integer n.


Output

For each test case on different lines print the answer to the problem.

Constraints

1 <= T <= 10
1 <= n <= 10^9

Example

Input:
10
1
2
3
4
5
6
7
8
9
10

Output:
0
0
0
1
0
0
1
1
0
0

Author:         sereja
Tester:         shangjingbo
Tags            sereja
Date Added:     25-05-2013
Time Limit:     1 sec
Source Limit:   50000 Bytes
'''

import sys

#### codechef 2013-10 Maxim and Dividers

def is_good(i):
    for c in str(i):
        if c in ('4','7'):
            return True
    return False
    
def solve(N):
    i = 1; ans = 0
    while i*i <= N:
        if N % i == 0:
            if is_good(i):
                ans += 1
            j = N/i
            if j != i and is_good(j):
                ans += 1
        i += 1
    return ans

def check_test(A, B, data='', case=[0]):
    print
    print "test %d:" % case[0]
    print A
    if A != B:
        if data:
            print data
        print '>>>', A
        print '<<<', B
        print "!!!!!!!! FAIL !!!!!!!!"
    else:
        print ":::::::) OK"
    case[0] += 1

def unit_test():
    print
    A, ans = 1, 0
    check_test(solve(A), ans, A)

    A, ans = 2, 0
    check_test(solve(A), ans, A)

    A, ans = 3, 0
    check_test(solve(A), ans, A)

    A, ans = 4, 1
    check_test(solve(A), ans, A)

    A, ans = 5, 0
    check_test(solve(A), ans, A)

    A, ans = 6, 0
    check_test(solve(A), ans, A)

    A, ans = 7, 1
    check_test(solve(A), ans, A)

    A, ans = 8, 1
    check_test(solve(A), ans, A)

    A, ans = 9, 0
    check_test(solve(A), ans, A)

    A, ans = 10, 0
    check_test(solve(A), ans, A)

    A = 10**9
    print solve(A)

def output():
    stdin = sys.stdin
    for case in xrange(1, int(stdin.next()) + 1):
        A = int(stdin.next())
        ans = solve(A)
        print ans

if __name__ == '__main__':
#    unit_test()
    output()