Valid Passcodes Divisible by D

You are given a list of integers. Each integer D represents a divisor. A valid passcode is defined as any 9-digit number that is a permutation of the digits 1 to 9 (each digit is used exactly once). Your task is to count the number of valid passcodes that are divisible by D.

Formally, consider all numbers formed by permuting the digits \(1, 2, \ldots, 9\). For a given divisor \(D\), you need to determine how many of these unique numbers \(N\) satisfy:

\( N \equiv 0 \pmod{D} \)

For example, when \(D=1\), every permutation is valid, hence there are \(9! = 362880\) valid passcodes. However, for a divisor such as \(D=10000\), there are no valid passcodes.

inputFormat

The input consists of multiple test cases. The first line contains a single integer \(T\) indicating the number of test cases. Each of the following \(T\) lines contains an integer \(D\), the divisor.

outputFormat

For each test case, output a single integer representing the number of valid passcodes (9-digit permutations of the digits 1 to 9) that are divisible by \(D\). Each result should be printed on a separate line.

## sample

3
1
10000
7

362880
0
51840

</p>