문제

민용이는 모든 양의 정수 $x$에 대하여 다음과 같이 정의된 함수 $f(x)$를 공부하고 있다.

• 만약 $x$의 자릿수 중 $0$이나 $1$이 아닌 숫자가 하나라도 있다면, $x$의 각 자릿수에 대하여 홀수인 숫자는 $1$로, 짝수인 숫자는 $0$으로 바꾼 값을 반환한다.
• 만약 $x$의 모든 자릿수가 $0$ 또는 $1$이라면, $x-1$을 반환한다.

양의 정수 $x$ ($1 \le x < 10^{2 \cdot 10^5}$)가 주어졌을 때, $x$가 $0$이 될 때까지 함수 $f$를 몇 번 적용해야 하는지 구하시오. 이 값은 매우 커질 수 있으므로, $10^9+7$로 나눈 나머지를 출력한다.

입력

첫째 줄에 테스트 케이스의 개수 $T$ ($1 \le T \le 10^5$)가 주어진다.

이어서 $T$개의 줄에 각 테스트 케이스에 해당하는 양의 정수 $x$가 주어진다. $x$는 $0$에서 $9$ 사이의 숫자로만 구성되어 있으며, 맨 앞자리에 $0$이 오는 경우는 없다.

모든 테스트 케이스에 주어지는 $x$의 자릿수의 총합은 $10^6$을 넘지 않는다.

출력

각 테스트 케이스마다 $x$가 $0$이 되기 위해 $f$를 적용해야 하는 횟수를 $10^9+7$로 나눈 나머지를 한 줄에 하나씩 출력한다.

예제 입력 1

2
24680
210

예제 출력 1

1
4

예제 입력 2

1
1234567890123456789012345678901234567890

예제 출력 2

511620083

제약 조건

• 테스트 케이스 3~5: $T \le 2\,000$, $x < 10^9$
• 테스트 케이스 6~7: $x < 10^{18}$
• 테스트 케이스 8~9: $x < 10^{60}$
• 테스트 케이스 10~12: 추가 제약 조건 없음.