解题思路

给定正整数 $m$，统计满足以下条件且不大于 $m$ 的整数个数：

• $n$ 的十进制表示是单调不降（上升数）；
• $n^2$ 的十进制表示也单调不降（超级上升数）。

核心做法：预处理 + 二分

1. 先写一个判定函数 is_nondec(x)：检查整数的十进制数字是否从左到右单调不降。

题目内容

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

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

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

输入描述

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

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

输出描述

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

样例1

输入

3
5
8
13

输出

5
7
9

说明

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