T404631 距离

#%RTGGv&&HGT*&T^F^%F&G*&T*

小L在学习了直线距离和曼哈顿距离后觉得十分无聊，于是自己抽象出了 $L-距离$ 的含义。定义两点 $(x_1,y_1)$ 和 $(x_2,y_2)$ 的 $L-距离$ 为 $L(x_1,x_2)+L(y_1,y_2)$。设 $x=\overline{x_1 x_2 x_3 \dots x_n}$，$y=\overline{y_1 y_2 y_3 \dots y_n}$，则令 $L(x,y)=\max(\{ 1 \le i \le n \mid x_i \ne y_i \})$（$\max(\emptyset) = 0$）。 现在小L有 $10^{2n}$ 次方个点，分别为 $(0,0),(0,1) \dots (10^n - 1,10^n - 1)$ 小L要将这些点重新排布，使得相邻两点间的 $L-距离$ 之和最小，问这个最小值。

此题有多组数据。 第一行一个整数 $t$ 表示数据组数。 接下来 $t$ 行，每行一个整数 $n$ （$1 \le n \le 10^{18}$），含义见上。

$t$ 行，每行一个整数表示最小值，只要求对 $10^9+7$（一个质数）取模。

$1 \le t \le 7 \times 10^5,1 \le n \le 10^{18}$