ZOJ Problem Set - 3842
Cirno's perfect math class is fashionable over the world. But now, sadly, it must be stopped for some reason. In the last class, N students attended, and each student gave a gift to Cirno. But the gifts are too many so that Cirno just want to take K(K is non-negative) gifts away.
As we all know, Cirno loves the number ⑨. Assume there are P ways to take away K gifts. If P > 0 and P is a multiple of 9, Cirno will accept K as an alternative plan. Now, Cirno want to know how many plans that she has to think over.
The number of test cases T(integer, about 50) will be given in the first line. Then T lines follow. and each line contains a non-negative integer N(N <= 10^1000).
One line for each case, the answer.
3 5 9 10
0 6 3
Author: LIN, Hanzhao
Source: ZOJ Monthly, January 2015