#y1023. sum

sum

Description

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

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

有一个序列 FF,F1=F2=1F_1=F_2=1,Fi=Fi−1+Fi−2(i≥3)F_i=F_{i-1}+F_{i-2}(i\ge 3)

对于数字 nn,求 f(∑i=1nf(Fi))f(\sum\limits_{i=1}^{n}f(F_i))。

Format

Input

一个整数 TT。

接下来 TT 行每行一个数 nn。

Output

TT 个整数,即答案。

Samples

1
5
3

Limitation

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

相关

在下列比赛中:

ACM