1	0
2	0
3	0
4	0
5	0
6	0
7	0
8	0
9	0
10	0
11	0
12	0
13	1
14	0
15	0
16	1
17	1
18	0
19	2
20	1
21	1
22	2
23	2
24	1
25	4
26	2
27	2
28	4
29	4
30	2
31	6
32	4
33	4
34	6
35	6
36	4
37	9
38	6
39	6
40	9
41	9
42	6
43	12
44	9
45	9
46	12
47	12
48	9
49	16
50	12
51	12
52	16
53	16
54	12
55	20
56	16
57	16
58	20
59	20
60	16
61	25
62	20
63	20
64	25
65	25
66	20
67	30
68	25
69	25
70	30
71	30
72	25
73	36
74	30
75	30
76	36
77	36
78	30
79	42
80	36
81	36
82	42
83	42
84	36
85	49
86	42
87	42
88	49
89	49
90	42
91	56
92	49
93	49
94	56
95	56
96	49
97	64
98	56
99	56
100	64
101	64
102	56
103	72
104	64
105	64
106	72
107	72
108	64
109	81
110	72
111	72
112	81
113	81
114	72
115	90
116	81
117	81
118	90
119	90
120	81
121	100
122	90
123	90
124	100
125	100
126	90
127	110
128	100
129	100
130	110
131	110
132	100
133	121
134	110
135	110
136	121
137	121
138	110
139	132
140	121
141	121
142	132
143	132
144	121
145	144
146	132
147	132
148	144
149	144
150	132
151	156
152	144
153	144
154	156
155	156
156	144
157	169
158	156
159	156
160	169
161	169
162	156
163	182
164	169
165	169
166	182
167	182
168	169
169	196
170	182
171	182
172	196
173	196
174	182
175	210
176	196
177	196
178	210
179	210
180	196
181	225
182	210
183	210
184	225
185	225
186	210
187	240
188	225
189	225
190	240
191	240
192	225
193	256
194	240
195	240
196	256
197	256
198	240
199	272
200	256
201	256
202	272
203	272
204	256
205	289
206	272
207	272
208	289
209	289
210	272
211	306
212	289
213	289
214	306
215	306
216	289
217	324
218	306
219	306
220	324
221	324
222	306
223	342
224	324
225	324
226	342
227	342
228	324
229	361
230	342
231	342
232	361
233	361
234	342
235	380
236	361
237	361
238	380
239	380
240	361
241	400
242	380
243	380
244	400
245	400
246	380
247	420
248	400
249	400
250	420
251	420
252	400
253	441
254	420
255	420
256	441
257	441
258	420
259	462
260	441
261	441
262	462
263	462
264	441
265	484
266	462
267	462
268	484
269	484
270	462
271	506
272	484
273	484
274	506
275	506
276	484
277	529
278	506
279	506
280	529
281	529
282	506
283	552
284	529
285	529
286	552
287	552
288	529
289	576
290	552
291	552
292	576
293	576
294	552
295	600
296	576
297	576
298	600
299	600
300	576
301	625
302	600
303	600
304	625
305	625
306	600
307	650
308	625
309	625
310	650
311	650
312	625
313	676
314	650
315	650
316	676
317	676
318	650
319	702
320	676
321	676
322	702
323	702
324	676
325	729
326	702
327	702
328	729
329	729
330	702
331	756
332	729
333	729
334	756
335	756
336	729
337	784
338	756
339	756
340	784
341	784
342	756
343	812
344	784
345	784
346	812
347	812
348	784
349	841
350	812
351	812
352	841
353	841
354	812
355	870
356	841
357	841
358	870
359	870
360	841
361	900
362	870
363	870
364	900
365	900
366	870
367	930
368	900
369	900
370	930
371	930
372	900
373	961
374	930
375	930
376	961
377	961
378	930
379	992
380	961
381	961
382	992
383	992
384	961
385	1024
386	992
387	992
388	1024
389	1024
390	992
391	1056
392	1024
393	1024
394	1056
395	1056
396	1024
397	1089
398	1056
399	1056
400	1089
401	1089
402	1056
403	1122
404	1089
405	1089
406	1122
407	1122
408	1089
409	1156
410	1122
411	1122
412	1156
413	1156
414	1122
415	1190
416	1156
417	1156
418	1190
419	1190
420	1156
421	1225
422	1190
423	1190
424	1225
425	1225
426	1190
427	1260
428	1225
429	1225
430	1260
431	1260
432	1225
433	1296
434	1260
435	1260
436	1296
437	1296
438	1260
439	1332
440	1296
441	1296
442	1332
443	1332
444	1296
445	1369
446	1332
447	1332
448	1369
449	1369
450	1332
451	1406
452	1369
453	1369
454	1406
455	1406
456	1369
457	1444
458	1406
459	1406
460	1444
461	1444
462	1406
463	1482
464	1444
465	1444
466	1482
467	1482
468	1444
469	1521
470	1482
471	1482
472	1521
473	1521
474	1482
475	1560
476	1521
477	1521
478	1560
479	1560
480	1521
481	1600
482	1560
483	1560
484	1600
485	1600
486	1560
487	1640
488	1600
489	1600
490	1640
491	1640
492	1600
493	1681
494	1640
495	1640
496	1681
497	1681
498	1640
499	1722
500	1681
501	1681
502	1722
503	1722
504	1681
505	1764
506	1722
507	1722
508	1764
509	1764
510	1722
511	1806
512	1764
513	1764
514	1806
515	1806
516	1764
517	1849
518	1806
519	1806
520	1849
521	1849
522	1806
523	1892
524	1849
525	1849
526	1892
527	1892
528	1849
529	1936
530	1892
531	1892
532	1936
533	1936
534	1892
535	1980
536	1936
537	1936
538	1980
539	1980
540	1936
541	2025
542	1980
543	1980
544	2025
545	2025
546	1980
547	2070
548	2025
549	2025
550	2070
551	2070
552	2025
553	2116
554	2070
555	2070
556	2116
557	2116
558	2070
559	2162
560	2116
561	2116
562	2162
563	2162
564	2116
565	2209
566	2162
567	2162
568	2209
569	2209
570	2162
571	2256
572	2209
573	2209
574	2256
575	2256
576	2209
577	2304
578	2256
579	2256
580	2304
581	2304
582	2256
583	2352
584	2304
585	2304
586	2352
587	2352
588	2304
589	2401
590	2352
591	2352
592	2401
593	2401
594	2352
595	2450
596	2401
597	2401
598	2450
599	2450
600	2401
601	2500
602	2450
603	2450
604	2500
605	2500
606	2450
607	2550
608	2500
609	2500
610	2550
611	2550
612	2500
613	2601
614	2550
615	2550
616	2601
617	2601
618	2550
619	2652
620	2601
621	2601
622	2652
623	2652
624	2601
625	2704
626	2652
627	2652
628	2704
629	2704
630	2652
631	2756
632	2704
633	2704
634	2756
635	2756
636	2704
637	2809
638	2756
639	2756
640	2809
641	2809
642	2756
643	2862
644	2809
645	2809
646	2862
647	2862
648	2809
649	2916
650	2862
651	2862
652	2916
653	2916
654	2862
655	2970
656	2916
657	2916
658	2970
659	2970
660	2916
661	3025
662	2970
663	2970
664	3025
665	3025
666	2970
667	3080
668	3025
669	3025
670	3080
671	3080
672	3025
673	3136
674	3080
675	3080
676	3136
677	3136
678	3080
679	3192
680	3136
681	3136
682	3192
683	3192
684	3136
685	3249
686	3192
687	3192
688	3249
689	3249
690	3192
691	3306
692	3249
693	3249
694	3306
695	3306
696	3249
697	3364
698	3306
699	3306
700	3364
701	3364
702	3306
703	3422
704	3364
705	3364
706	3422
707	3422
708	3364
709	3481
710	3422
711	3422
712	3481
713	3481
714	3422
715	3540
716	3481
717	3481
718	3540
719	3540
720	3481
721	3600
722	3540
723	3540
724	3600
725	3600
726	3540
727	3660
728	3600
729	3600
730	3660
731	3660
732	3600
733	3721
734	3660
735	3660
736	3721
737	3721
738	3660
739	3782
740	3721
741	3721
742	3782
743	3782
744	3721
745	3844
746	3782
747	3782
748	3844
749	3844
750	3782
751	3906
752	3844
753	3844
754	3906
755	3906
756	3844
757	3969
758	3906
759	3906
760	3969
761	3969
762	3906
763	4032
764	3969
765	3969
766	4032
767	4032
768	3969
769	4096
770	4032
771	4032
772	4096
773	4096
774	4032
775	4160
776	4096
777	4096
778	4160
779	4160
780	4096
781	4225
782	4160
783	4160
784	4225
785	4225
786	4160
787	4290
788	4225
789	4225
790	4290
791	4290
792	4225
793	4356
794	4290
795	4290
796	4356
797	4356
798	4290
799	4422
800	4356
801	4356
802	4422
803	4422
804	4356
805	4489
806	4422
807	4422
808	4489
809	4489
810	4422
811	4556
812	4489
813	4489
814	4556
815	4556
816	4489
817	4624
818	4556
819	4556
820	4624
821	4624
822	4556
823	4692
824	4624
825	4624
826	4692
827	4692
828	4624
829	4761
830	4692
831	4692
832	4761
833	4761
834	4692
835	4830
836	4761
837	4761
838	4830
839	4830
840	4761
841	4900
842	4830
843	4830
844	4900
845	4900
846	4830
847	4970
848	4900
849	4900
850	4970
851	4970
852	4900
853	5041
854	4970
855	4970
856	5041
857	5041
858	4970
859	5112
860	5041
861	5041
862	5112
863	5112
864	5041
865	5184
866	5112
867	5112
868	5184
869	5184
870	5112
871	5256
872	5184
873	5184
874	5256
875	5256
876	5184
877	5329
878	5256
879	5256
880	5329
881	5329
882	5256
883	5402
884	5329
885	5329
886	5402
887	5402
888	5329
889	5476
890	5402
891	5402
892	5476
893	5476
894	5402
895	5550
896	5476
897	5476
898	5550
899	5550
900	5476
901	5625
902	5550
903	5550
904	5625
905	5625
906	5550
907	5700
908	5625
909	5625
910	5700
911	5700
912	5625
913	5776
914	5700
915	5700
916	5776
917	5776
918	5700
919	5852
920	5776
921	5776
922	5852
923	5852
924	5776
925	5929
926	5852
927	5852
928	5929
929	5929
930	5852
931	6006
932	5929
933	5929
934	6006
935	6006
936	5929
937	6084
938	6006
939	6006
940	6084
941	6084
942	6006
943	6162
944	6084
945	6084
946	6162
947	6162
948	6084
949	6241
950	6162
951	6162
952	6241
953	6241
954	6162
955	6320
956	6241
957	6241
958	6320
959	6320
960	6241
961	6400
962	6320
963	6320
964	6400
965	6400
966	6320
967	6480
968	6400
969	6400
970	6480
971	6480
972	6400
973	6561
974	6480
975	6480
976	6561
977	6561
978	6480
979	6642
980	6561
981	6561
982	6642
983	6642
984	6561
985	6724
986	6642
987	6642
988	6724
989	6724
990	6642
991	6806
992	6724
993	6724
994	6806
995	6806
996	6724
997	6889
998	6806
999	6806
1000	6889