题目描述

斐波那契数列的递推公式为: $F_n=F_{n−1}+F_{n−2}$，其中 $F_1=F_2=1$。

请问, 斐波那契数列的第 $1$ 至 $N$ 项（含）中, 有多少项的个位是 7。

输入描述

第一行包一个整数 $T$，表示测试数据的规模。

接下来 $T$ 行每行 $1$ 个整数 $N$。

输出描述

对每个输入输出一个整数表示答案。

2
40
2019

6
270

评测用例规模与约定：

对于所有评测用例，$1≤T≤1000，1≤N≤10^{18}$。