{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eThis problem is based on an exercise of David Hilbert, who pedagogically suggested that one study the theory of \u003cem\u003e4n+1\u003c/em\u003e numbers. Here, we do only a bit of that. \u003c/p\u003e\u003cp\u003eAn \u003cb\u003eH\u003c/b\u003e-number is a positive number which is one more than a multiple of four: 1, 5, 9, 13, 17, 21,... are the \u003cb\u003eH\u003c/b\u003e-numbers. For this problem we pretend that these are the \u003cem\u003eonly\u003c/em\u003e numbers. The \u003cb\u003eH\u003c/b\u003e-numbers are closed under multiplication. \u003c/p\u003e\u003cp\u003eAs with regular integers, we partition the \u003cb\u003eH\u003c/b\u003e-numbers into units, \u003cb\u003eH\u003c/b\u003e-primes, and \u003cb\u003eH\u003c/b\u003e-composites. 1 is the only unit. An \u003cb\u003eH\u003c/b\u003e-number \u003ci\u003eh\u003c/i\u003e is \u003cb\u003eH\u003c/b\u003e-prime if it is not the unit, and is the product of two \u003cb\u003eH\u003c/b\u003e-numbers in only one way: 1 × \u003ci\u003eh\u003c/i\u003e. The rest of the numbers are \u003cb\u003eH\u003c/b\u003e-composite. \u003c/p\u003e\u003cp\u003eFor examples, the first few \u003cb\u003eH\u003c/b\u003e-composites are: 5 × 5 \u003d 25, 5 × 9 \u003d 45, 5 × 13 \u003d 65, 9 × 9 \u003d 81, 5 × 17 \u003d 85. \u003c/p\u003e\u003cp\u003eYour task is to count the number of \u003cb\u003eH\u003c/b\u003e-semi-primes. An \u003cb\u003eH\u003c/b\u003e-semi-prime is an \u003cb\u003eH\u003c/b\u003e-number which is the product of exactly two \u003cb\u003eH\u003c/b\u003e-primes. The two \u003cb\u003eH\u003c/b\u003e-primes may be equal or different. In the example above, all five numbers are \u003cb\u003eH\u003c/b\u003e-semi-primes. 125 \u003d 5 × 5 × 5 is not an \u003cb\u003eH\u003c/b\u003e-semi-prime, because it\u0027s the product of three \u003cb\u003eH\u003c/b\u003e-primes. \u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eEach line of input contains an \u003cb\u003eH\u003c/b\u003e-number ≤ 1,000,001. The last line of input contains 0 and this line should not be processed. \u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eFor each inputted \u003cb\u003eH\u003c/b\u003e-number \u003ci\u003eh\u003c/i\u003e, print a line stating \u003ci\u003eh\u003c/i\u003e and the number of \u003cb\u003eH\u003c/b\u003e-semi-primes between 1 and \u003ci\u003eh\u003c/i\u003e inclusive, separated by one space in the format shown in the sample. \u003c/p\u003e"}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e21 \r\n85\r\n789\r\n0\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e21 0\r\n85 5\r\n789 62\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}