Welcome to ZOJ
 Problem Sets Information Select Problem Runs Ranklist
ZOJ Problem Set - 3842
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