Welcome to ZOJ
 Contests Information Problems Runs Statistics Ranklist Clarification
138 - ZOJ Monthly, January 2015 - C
Cirno's Perfect Math Class

Time Limit: 2 Seconds      Memory Limit: 65536 KB

"Minnaa ~ Cirno no Sansuu Kyoushitsu Hajimaruyo ~ "

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.

#### Input

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).

#### Output

One line for each case, the answer.

```3
5
9
10
```

#### Sample Output

```0
6
3
```

Author: LIN, Hanzhao
Submit    Status