For all positive integers x, the function f(x) is defined as follows:
If x has any digits that aren't 0 or 1, for each digit of x, set it to 1, if it is odd or 0
otherwise, and return x.
Otherwise, return x−1.
Given a value of x (1≤x<
), find how many times f needs to be applied to x until x reaches 0. As this number might be very large, output its remainder when divided by 109+7.
INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains T (1≤T≤105), the number of independent tests.
The next T lines each contain a positive integer x consisting solely of the digits 0-9, with no leading zeros.
It is guaranteed that the total number of digits in all input integers does not exceed 106 .
OUTPUT FORMAT (print output to the terminal / stdout):
For each test case, output the remainder of the number of times when divided by 109+7 on a separate line.
SAMPLE INPUT:
2
24680
210
SAMPLE OUTPUT:
1
4
First test: x becomes zero after one operation.
Second test: f(x)=10,f2(x)=9,f3(x)=1,f4(x)=0
SAMPLE INPUT:
1
1234567890123456789012345678901234567890
SAMPLE OUTPUT:
511620083
SCORING:
Inputs 3-5: T≤2000, x<109
Inputs 6-7: x<1018
Inputs 8-9: x<1060
Inputs 10-12: No additional constraints.
Problem credits: Aidan Bai