H-준소수 세기

이 문제는 다비트 힐베르트(David Hilbert)가 $4n+1$ 꼴의 수에 대한 이론을 연구해 보라고 제안한 연습 문제에서 비롯되었습니다. 여기서는 그 이론의 아주 작은 일부만 다룹니다.

H-수는 4의 배수보다 1 큰 양의 정수입니다. 즉 $1, 5, 9, 13, 17, 21, \dots$ 가 H-수입니다. 이 문제에서는 이 수들만 존재한다고 가정합니다. H-수들은 곱셈에 대해 닫혀 있습니다.

보통의 정수와 마찬가지로 H-수를 단위원(unit), H-소수, H-합성수로 나눕니다. 단위원은 $1$ 하나뿐입니다. H-수 $h$가 단위원이 아니면서 두 H-수의 곱으로 나타내는 방법이 $1 \times h$ 한 가지뿐이면 $h$를 H-소수라고 합니다. 나머지 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-준소수가 아닙니다.

각 줄에는 $1 \le h \le 1000001$ 을 만족하는 H-수 $h$가 하나씩 주어집니다. 마지막 줄에는 $0$이 주어지며, 이 줄은 처리하지 않습니다.

입력으로 주어진 각 H-수 $h$에 대해, $h$와 $1$ 이상 $h$ 이하의 H-준소수의 개수를 공백 하나로 구분하여 한 줄에 출력합니다.