You are given \(S\). Determine the number of possible values of \(N\) that satisfy the following condition:

You are given \(N\) where represents a number that is generated by shifting the digits of \(N\) cyclically towards left by \(i\) units.

Also, \(N\) must satisfy the provided condition:

\(S\) is the summation \(\{ F(N,i) \}\) for all \(i\) from 0 to \(|N| - 1\) where \(|N|\) represents the number of digits in \(N\).

\(N\) can have leading zeroes. As the number of \(N\) can be very large, print it modulo \(1000000000 + 7\).

Input format

• The first line contains an integer \(Q\) denoting the number of queries.
• The next \(Q\) lines contain an integer \(S\).

Output format

Print a single integer in a separate line corresponding to each query.

Constraints
\(1 \le Q \le 1e5\\ 1 \le S \le 1e18  \)