For all positive integers , the function is defined as follows:
If has any digits that aren't or , for each digit of , set it to if it is odd or otherwise, and return .
Otherwise, return .
Given a value of (), find how many times needs to be applied to until reaches . As this number might be very large, output its remainder when divided by .
输入格式
The first line contains (), the number of independent tests.
The next lines each contain a positive integer 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 .
输出格式
For each test case, output the remainder of the number of times when divided by on a separate line.
