Strange Function
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<102⋅105), 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.
First test: x becomes zero after one operation.
Second test: f(x)=10,f2(x)=9,f3(x)=1,f4(x)=0
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
Source: USA Computing Olympiad.
Input Format
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
For each test case, output the remainder of the number of times when divided by 109+7 on a separate line.