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.

#### Sample Input

3
5
9
10

#### Sample Output

0
6
3

Author:

**LIN, Hanzhao**
Source:

**ZOJ Monthly, January 2015**
Submit
Status