考虑以以下开头的无限整数序列 S：
$S=1,1,2,1,3,2,4,1,5,3,6,2,7,8,4,9,1,10,11,5,\dots$

圈出每个整数第一次出现的位置。
$S=\overline{)1},1,\overline{)2},1,\overline{)3},2,\overline{)4},1,\overline{)5},3,\overline{)6},2,\overline{)7},\overline{)8},4,\overline{)9},1,\overline{)10},\overline{)11},5,\dots$

该序列具有以下属性：

• 圈出的数字是从 $1$ 开始的连续整数。
• 紧邻每个非圆圈数字 $a_i$ 之前，正好有 $\lfloor \sqrt{a_i}\rfloor$ 相邻的圆圈数字，其中 $\lfloor \rfloor$ 是下取整函数。
• 如果我们删除所有带圆圈的数字，剩余的数字将形成与 $S$ 相同的序列，因此 $S$ 是一个分形序列。

设 $T(n)$ 为序列中前 $n$ 个元素的总和。
您将得到 $T(1)=1$、$T(20)=86$、$T({10}^3)=364089$ 和 $T({10}^9)=498676527978348241$。

查找$T({10}^{18})$。请给出答案的最后 $9$ 数字。