配点 : 475点

問題文

NN 桁の 66 の倍数の各桁の和」の総和を求めてください。
ただし、答えが非常に大きくなる可能性があるので 109+710^9+7 で割ったあまりを出力してください。
TT 個のテストケースが与えられるので、それぞれに答えてください。

制約

  • 1T3001≦T≦300
  • 1N3001≦N≦300
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

TT
case1case_1
case2case_2
\vdots
case3case_3

各テストケースは以下の形式で与えられる。

NN

出力

TT 行出力してください。ii 行目には、 caseicase_i に対する答えを出力してください。


入出力例1

  • 入力
2
2
3
  • 出力
135
2025

22 桁で 66 の倍数であるものは、12,18...9612, 18 ... 96 であり、それぞれの各桁の和は 3,9...153, 9 ... 15 です。
これらの総和は 135135 であるので、135135 を出力します。


入出力例2

  • 入力
2
100
200
  • 出力
304457820
252156756

109+710^9+7 で割ったあまりを出力することに注意してください。

Submit


Go (1.21)