Welcome to ZOJ
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