UVA11105 Semi-prime H-numbers

本题源于大卫·希尔伯特（David Hilbert）的一个教学练习，他曾建议研究 $4n + 1$ 数的性质。这里我们只探讨其中一小部分。 H 数是指那些比 $4$ 的倍数多 $1$ 的正整数：```1, 5, 9, 13, 17, 21, ... ``` 都是 H 数。在本题中，我们假定这些就是全部的数。H 数集在乘法下是封闭的。 与常规整数类似，我们将 H 数划分为单位、H 素数和 H 合数。1 是唯一的单位。一个 H 数 $h$ 被称为 H 素数，如果它不是单位，并且只能表示为两个 H 数的乘积：$1 \times h$。其余的数则称为 H 合数。 例如，前几个 H 合数有：$5 \times 5 = 25$，$5 \times 9 = 45$，$5 \times 13 = 65$，$9 \times 9 = 81$，$5 \times 17 = 85$。 你的任务是统计 H 半素数的个数。H 半素数是指恰好可以表示为两个 H 素数乘积的 H 数，这两个 H 素数可以相等也可以不同。在上面的例子中，所有五个数都是 H 半素数。而 $125 = 5 \times 5 \times 5$ 不是 H 半素数，因为它是三个 H 素数的乘积。

每行输入包含一个 H 数 $h$，满足 $h \leq 1,000,001$。最后一行包含 0，表示输入结束，该行不应被处理。

对于每个输入的 H 数 $h$，输出一行，包含 $h$ 以及从 1 到 $h$（含）之间的 H 半素数个数，两者之间用一个空格分隔，格式如样例所示。