> 许多人的人生就像是旋转木马这般，虽永不停歇的旋转，看似死水一般，有起有伏，但身旁的风景却一直在变化着，我们还是能够乐在其中，也还是能够一直向前。 > > 🎵[《Merry-Go-Round》 - 久石让 (ひさいし じょう)](https://y.qq.com/n/ryqq/songDetail/004dKaYD4MBAMb) <iframe frameborder="no" border="0" marginwidth="0" marginheight="0" width=330 height=86 src="//music.163.com/outchain/player?type=2&id=1805021102&auto=0&height=66"></iframe>  --- 你身在一个故事的平行世界里，拥有能力能够削弱女巫对苏菲施下的诅咒。 苏菲身上的诅咒值可以看作一个正整数 $a$，而你的能力可以将诅咒值降低 $b$ 点，且 $b$ 的数值会随着准备时间 $t$ 的变化而变化。 针对准备时间 $t$ 与数值 $b$ 之间的关系，如下所述： - 令 $f(x)$ 表示 $x$ 在十进制下各个数位上的数值之和，例如 $f(3)=3,\ f(56)=5+6=11$ - 令 $g(x)$ 表示 $f(1)$ 到 $f(x)$ 的平方和，即 $g(x)=\sum_{i=1}^xf(i)^2$，例如 $g(3)=f(1)^2+f(2)^2+f(3)^2=1+4+9=14$ - 令准备时间为 $t$，则满足 $b=g(t)^2$ 由于这项能力会消耗极大数量的法力，所以你只能够发动一次，并且想尽可能多地降低苏菲身上的诅咒值。但如果将诅咒值降低至 $0$ 以下，可能会对苏菲产生其它的不良影响，因此你最多只能够将诅咒值降低至 $0$。已知准备时间必是整数，试问准备时间最大为多少？

第一行包含一个正整数 $T\ (T\le 50000)$，表示测试数据组数。 每组测试数据占一行，仅包含一个正整数 $a\ (1\le a\le 10^{16})$，表示苏菲身上的诅咒值。

对于每组测试数据，在一行内输出一个整数，表示最大的准备时间。

答案不会超过 $2\cdot 10^5$ 哦。