题目内容

定义一个正整数 $n$ 是上升数，当且仅当其十进制表示为单调不降的，如 $11223,9$，反之 $114514,1919810$ 则不是。

定义一个正整数 $n$ 是超级上升数，当且仅当 $n$ 为上升数，且 $n^2$ 也为上升数。

现在包包有一个正整数 $m$。你需要求出有多少个不大于 $m$ 的超级上升数。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T(1≤T≤10^4)$ 代表数据组数，每组测试数据描述如下：

输入一行一个正整数 $m(1≤m≤10^{18})$ 。

输出描述

对于每组测试数据，输出一行一个整数，代表不大于 $m$ 的超级上升数的数量。

样例1

输入

3
5
8
13

输出

5
7
9

说明

不大于 $13$ 的超级上升数有：$1,2,3,4,5,6,7,12,13$ 。