Description

设函数 $s(x)$ 表示 $x$ 的每位数字之和，例如 $s(123)=1+2+3=6$。

函数 $f(x)=\underbrace{s(s(...s(x)...))}_{x\texttt{个}s}$。

有一个序列 $F$，$F_1=F_2=1$，$F_i=F_{i-1}+F_{i-2}(i\ge 3)$

对于数字 $n$，求 $f(\sum\limits_{i=1}^{n}f(F_i))$。

Format

Input

一个整数 $T$。

接下来 $T$ 行每行一个数 $n$。

Output

$T$ 个整数，即答案。

Samples

1
5

3

Limitation

$T\le 20,1\le n\le 10^{12}$