{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e\r\n\t\u003cp\u003e\r\n\t\tThis problem is based on an exercise of David \u003cspan data-scayt_word\u003d\"Hilbert\" data-scaytid\u003d\"1\"\u003eHilbert\u003c/span\u003e, who pedagogically suggested that one study the theory of \u003cem\u003e\u003cspan data-scayt_word\u003d\"4n\" data-scaytid\u003d\"2\"\u003e4n\u003c/span\u003e+1\u003c/em\u003e numbers. Here, we do only a bit of that.\u003c/p\u003e\r\n\t\u003cp\u003e\r\n\t\tAn \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\r\n\t\u003cp\u003e\r\n\t\tAs 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 \u0026times; \u003ci\u003eh\u003c/i\u003e. The rest of the numbers are \u003cb\u003eH\u003c/b\u003e-composite.\u003c/p\u003e\r\n\t\u003cp\u003e\r\n\t\tFor examples, the first few \u003cb\u003eH\u003c/b\u003e-composites are: 5 \u0026times; 5 \u003d 25, 5 \u0026times; 9 \u003d 45, 5 \u0026times; 13 \u003d 65, 9 \u0026times; 9 \u003d 81, 5 \u0026times; 17 \u003d 85.\u003c/p\u003e\r\n\t\u003cp\u003e\r\n\t\tYour 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 \u0026times; 5 \u0026times; 5 is not an \u003cb\u003eH\u003c/b\u003e-semi-prime, because it\u0026#39;s the product of three \u003cb\u003eH\u003c/b\u003e-primes.\u003c/p\u003e\r\n\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e\r\n\t\u003cp\u003e\r\n\t\tEach line of input contains an \u003cb\u003eH\u003c/b\u003e-number \u0026le; 1,000,001. The last line of input contains 0 and this line should not be processed.\u003c/p\u003e\r\n\u003c/div\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e\r\n\t\u003cp\u003e\r\n\t\tFor 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\r\n\u003c/div\u003e"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cpre class\u003d\"sio\"\u003e\r\n21 \r\n85\r\n789\r\n0\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cpre class\u003d\"sio\"\u003e\r\n21 0\r\n85 5\r\n789 62\u003c/pre\u003e"}}]}