1	1078
2	1063
3	1136
4	1643
5	1788
6	1945
7	2184
8	2240
9	2494
10	2831
11	3160
12	3021
13	2828
14	2267
15	1852
16	1444
17	1840
18	2434
19	2930
20	3378
21	3339
22	2691
23	2115
24	1896
25	2238
26	2426
27	2287
28	2144
29	1775
30	1575
31	1511
32	1543
33	1627
34	1649
35	1430
36	1200
37	946
38	744
39	642
40	651
41	617
42	921
43	1094
44	1357
45	1533
46	1471
47	1741
48	2043
49	2199
50	1688
51	1223
52	1004
53	1025
54	1333
55	1939
56	2073
57	1958
58	1432
59	1096
60	955
61	997
62	1173
63	916
64	988
65	1153
66	1682
67	2000
68	1882
69	1473
70	822
71	517
72	752
73	1304
74	1482
75	1542
76	1250
77	995
78	966
79	1242
80	1521
81	1545
82	1522
83	1746
84	1972
85	2406
86	2592
87	2500
88	2032
89	1420
90	1405
91	1389
92	1670
93	1826
94	2077
95	2090
96	2107
97	1926
98	1686
99	1860
100	2439
101	2567
102	2492
103	2322
104	2126
105	1839
106	1683
107	1644
108	1574
109	1487
110	1115
111	1109
112	1140
113	1256
114	1637
115	2248
116	3216
117	3857
118	4028
119	3248
120	2578
121	1997
122	1806
123	1447
124	1200
125	1146
126	1047
127	1062
128	1166
129	1244
130	1150
131	890
132	769
133	722
134	994
135	1760
136	2426
137	2781
138	2308
139	1526
140	1226
141	1176
142	1328
143	1120
144	856
145	492
146	377
147	339
148	430
149	670
150	933
151	895
152	788
153	740
154	653
155	1148
156	1783
157	2309
158	2359
159	2016
160	1352
161	1492
162	2070
163	2185
164	1927
165	1492
166	1378
167	1668
168	2221
169	2677
170	2661
171	2015
172	1301
173	948
174	1515
175	2571
176	3060
177	2743
178	1987
179	1303
180	1409
181	1343
182	1032
183	994
184	1083
185	1326
186	2172
187	2421
188	1949
189	1078
190	589
191	580
192	382
193	353
194	585
195	853
196	1523
197	2311
198	2527
199	2397
200	2003
201	1239
202	969
203	1104
204	1307
205	1414
206	1337
207	1283
208	1550
209	2239
210	3005
211	3504
212	3047
213	2165
214	1239
215	840
216	766
217	1407
218	1898
219	2126
220	1836
221	1524
222	1329
223	1644
224	1953
225	2538
226	2605
227	2382
228	2355
229	2178
230	2180
231	2169
232	1972
233	1459
234	940
235	718
236	533
237	682
238	1236
239	1519
240	1868
241	1932
242	2208
243	2198
244	2044
245	1848
246	1837
247	2280
248	2628
249	2172
250	1455
251	1002
252	903
253	970
254	1080
255	1282
256	1533
257	1587
258	957
259	563
260	297
261	259
262	121
263	32
264	346
265	333
266	392
267	210
268	-297
269	-298
270	98
271	487
272	769
273	1252
274	1537
275	1852
276	2000
277	1873
278	1531
279	1420
280	1731
281	1829
282	1643
283	1397
284	1269
285	958
286	777
287	532
288	802
289	1008
290	1036
291	1104
292	1069
293	1477
294	1545
295	1522
296	1291
297	1389
298	1437
299	1431
300	1322
301	1341
302	1343
303	1506
304	1544
305	1530
306	1361
307	1280
308	1153
309	1097
310	979
311	984
312	908
313	1022
314	1457
315	1856
316	2099
317	1762
318	1984
319	2435
320	2539
321	2409
322	2531
323	2534
324	2475
325	2365
326	2151
327	1368
328	738
329	815
330	1033
331	1106
332	905
333	1135
334	1579
335	1775
336	1525
337	1394
338	1864
339	2436
340	2748
341	2632
342	2059
343	1939
344	2052
345	1964
346	1827
347	1790
348	1723
349	1336
350	1008
351	977
352	919
353	948
354	508
355	552
356	770
357	1025
358	1232
359	816
360	737
361	1110
362	1273
363	1613
364	1672
365	1547
366	1413
367	1627
368	1629
369	1749
370	1660
371	1643
372	1612
373	1741
374	1625
375	1485
376	1000
377	957
378	973
379	1352
380	1270
381	894
382	831
383	1496
384	3063
385	3798
386	3273
387	1927
388	1336
389	1334
390	1628
391	1496
392	1497
393	1531
394	1698
395	2116
396	2757
397	2724
398	2393
399	2094
400	2599
401	3079
402	3189
403	2781
404	2684
405	2619
406	2918
407	3211
408	2989
409	2592
410	2496
411	2144
412	2100
413	2930
414	3850
415	4049
416	3174
417	2049
418	1821
419	2536
420	3577
421	3725
422	3373
423	2832
424	2075
425	1495
426	1270
427	1153
428	1504
429	2276
430	2703
431	3049
432	2842
433	2208
434	1557
435	1395
436	1858
437	2105
438	2042
439	1924
440	2315
441	2832
442	2804
443	2624
444	1750
445	1402
446	1333
447	1368
448	1791
449	1777
450	1665
451	1720
452	1952
453	2390
454	2716
455	2968
456	3027
457	3087
458	3101
459	2934
460	2513
461	2062
462	1755
463	1791
464	2056
465	2120
466	2054
467	1950
468	2436
469	3283
470	3367
471	3330
472	3198
473	2317
474	1185
475	758
476	906
477	1612
478	2862
479	3448
480	2960
481	2458
482	3085
483	3670
484	2758
485	1825
486	1950
487	2609
488	2742
489	2122
490	1741
491	1927
492	2670
493	3018
494	3282
495	3646
496	3797
497	3402
498	3145
499	2907
500	2760
501	2393
502	2119
503	2623
504	3254
505	3476
506	3575
507	3113
508	2522
509	2076
510	2106
511	2932
512	4376
513	5051
514	4719
515	3582
516	3198
517	3547
518	4407
519	4604
520	3769
521	3042
522	2833
523	3319
524	3800
525	3340
526	2628
527	2380
528	2337
529	2653
530	2893
531	2386
532	1803
533	1700
534	2237
535	2492
536	1967
537	1133
538	1000
539	1591
540	2646
541	3277
542	3357
543	3026
544	2593
545	2180
546	2380
547	2481
548	2339
549	2745
550	3384
551	3751
552	3870
553	4016
554	3755
555	4061
556	3861
557	3934
558	4046
559	3414
560	2266
561	2671
562	3102
563	3125
564	2828
565	3538
566	4558
567	4401
568	3367
569	2822
570	3713
571	4834
572	5733
573	5343
574	5865
575	6599
576	6165
577	5159
578	4082
579	2976
580	3033
581	4149
582	5765
583	7034
584	8543
585	10367
586	10676
587	8623
588	6585
589	5619
590	5409
591	6177
592	6687
593	7009
594	7326
595	6902
596	5382
597	4480
598	4491
599	4428
600	5494
601	7209
602	6932
603	5924
604	5600
605	5505
606	4909
607	4394
608	5172
609	6094
610	6743
611	7146
612	6765
613	6547
614	6581
615	6598
616	6807
617	7175
618	6922
619	7362
620	6435
621	5411
622	6743
623	9659
624	10798
625	10603
626	9440
627	8288
628	7459
629	6377
630	6317
631	6869
632	6412
633	6225
634	8097
635	8874
636	8481
637	9540
638	8745
639	7889
640	8076
641	7778
642	7203
643	6295
644	5951
645	6898
646	7410
647	8048
648	8246
649	7681
650	8176
651	8580
652	9634
653	10152
654	8591
655	6603
656	5363
657	6057
658	7074
659	8219
660	8452
661	8303
662	7920
663	6555
664	6971
665	6734
666	5451
667	3489
668	3792
669	5870
670	7310
671	8114
672	7161
673	6579
674	6374
675	6566
676	7417
677	7091
678	5251
679	4512
680	4826
681	5195
682	4420
683	3771
684	2827
685	3639
686	4464
687	5268
688	5828
689	6114
690	6572
691	7677
692	7247
693	7259
694	5720
695	3745
696	3299
697	3319
698	3105
699	4247
700	5117
701	4664
702	4313
703	4779
704	4896
705	5011
706	4271
707	3235
708	3119
709	2678
710	2971
711	3718
712	3751
713	2742
714	2666
715	2836
716	2744
717	2729
718	2691
719	2843
720	3989
721	5055
722	3645
723	2049
724	1674
725	1935
726	2786
727	2664
728	2638
729	3089
730	3265
731	3778
732	3048
733	2047
734	2344
735	2870
736	2761
737	2379
738	3502
739	5295
740	5932
741	4750
742	4370
743	5281
744	3718
745	2517
746	2858
747	3544
748	3221
749	2815
750	2548
751	2188
752	1101
753	1009
754	2270
755	2340
756	1749
757	1222
758	1184
759	2237
760	3992
761	3783
762	2250
763	1675
764	2546
765	3774
766	4521
767	3526
768	2516
769	2758
770	2368
771	1846
772	1885
773	3303
774	5204
775	5396
776	4183
777	3152
778	2624
779	2970
780	4247
781	3702
782	2425
783	1620
784	926
785	1144
786	1807
787	3085
788	3433
789	3229
790	2199
791	2285
792	2186
793	1388
794	1320
795	1424
796	1941
797	2972
798	4544
799	4023
800	2270
801	2068
802	2243
803	2600
804	2762
805	2428
806	2013
807	2221
808	2178
809	1637
810	1522
811	1860
812	2184
813	1611
814	1527
815	2405
816	2966
817	2140
818	1217
819	1592
820	1876
821	2074
822	1447
823	948
824	884
825	1555
826	2587
827	1853
828	1482
829	1293
830	1364
831	1599
832	1099
833	541
834	797
835	951
836	1818
837	2963
838	3320
839	4059
840	3533
841	2152
842	2904
843	2714
844	2310
845	1283
846	1212
847	3223
848	3637
849	2249
850	1366
851	963
852	903
853	770
854	189
855	-310
856	291
857	423
858	828
859	1597
860	1473
861	778
862	669
863	780
864	795
865	790
866	1252
867	1520
868	1058
869	914
870	945
871	1841
872	3471
873	3332
874	1694
875	1237
876	949
877	1367
878	1556
879	1276
880	1367
881	1555
882	935
883	793
884	1034
885	678
886	570
887	971
888	1294
889	902
890	864
891	826
892	679
893	216
894	220
895	519
896	793
897	1775
898	1475
899	830
900	1079
901	970
902	1566
903	1742
904	1390
905	561
906	681
907	1852
908	1869
909	2451
910	2721
911	1960
912	1938
913	1894
914	1292
915	1032
916	610
917	410
918	1147
919	1524
920	678
921	805
922	1727
923	3651
924	3179
925	1463
926	1142
927	1445
928	1845
929	1830
930	1469
931	3076
932	4182
933	3209
934	3242
935	3466
936	2950
937	1779
938	720
939	893
940	1565
941	1410
942	892
943	715
944	1046
945	1563
946	1489
947	1520
948	1318
949	656
950	804
951	1052
952	995
953	858
954	867
955	1056
956	1077
957	1550
958	1585
959	1331
960	858
961	1092
962	963
963	450
964	469
965	615
966	950
967	669
968	926
969	1292
970	1353
971	1136
972	1216
973	1528
974	764
975	371
976	629
977	854
978	1087
979	631
980	947
981	777
982	461
983	469
984	680
985	648
986	1479
987	2011
988	2050
989	2015
990	1676
991	1704
992	1183
993	888
994	1887
995	1249
996	612
997	672
998	936
999	480
1000	424
1001	646
1002	1570
1003	721
1004	408
1005	846
1006	684
1007	661
1008	1539
1009	2779
1010	1259
1011	438
1012	333
1013	38
1014	96
1015	896
1016	430
1017	152
1018	139
1019	656
1020	644
1021	430
1022	362
1023	301
1024	467