9	5
10	28
11	132
12	1143
13	4728
14	15702
15	45941
16	53131
17	54825
18	54386
19	63491
20	97867
21	115680
22	128413
23	124487
24	449844
25	415665
26	408711
27	479040
28	552714
29	671357
30	703131
31	656138
32	600532
33	430005
34	263231
35	196469
36	225520
37	184019
38	126076
39	90223
40	59188
41	39461
42	31306
43	23701
44	17986
45	15321
46	15664
47	18475
48	21949
49	23816
50	23850
51	24084
52	21694
53	18517
54	16650
55	18290
56	23707
57	27018
58	28622
59	29510
60	30786
61	34645
62	47572
63	77955
64	144472
65	224589
66	244122
67	244288
68	239435
69	235571
70	234956
71	221207
72	197014
73	172748
74	137862
75	99539
76	66544
77	43335
78	28720
79	21479
80	19612
81	21034
82	26091
83	40261
84	37048
85	34644
86	32899
87	31068
88	36530
89	46952
90	48135
91	49729
92	56103
93	62535
94	67783
95	67832
96	67101
97	66617
98	70122
99	79784
100	91474
101	106530
102	117145
103	123983
104	130435
105	141070
106	167820
107	187932
108	209392
109	227579
110	243362
111	250751
112	254604
113	250221
114	252136
115	245230
116	238785
117	228671
118	215256
119	205716
120	196684
121	191089
122	186978
123	179288
124	183427
125	189591
126	267935
127	298297
128	279416
129	254856
130	236687
131	238582
132	235038
133	236288
134	245206
135	258751
136	269363
137	280530
138	296202
139	322316
140	360525
141	396415
142	412504
143	417096
144	410760
145	403206
146	394615
147	386012
148	379266
149	372629
150	369155
151	365906
152	372086
153	376448
154	387997
155	414030
156	451016
157	511921
158	588668
159	647203
160	685648
161	709202
162	736140
163	778046
164	831191
165	874039
166	973853
167	1135645
168	1242262
169	1276178
170	1276324
171	1288613
172	1324805
173	1357897
174	1377181
175	1381256
176	1397257
177	1476854
178	1567173
179	1657468
180	1716909
181	1864109
182	2112245
183	2361878
184	2526646
185	2609655
186	2661218
187	2705544
188	2724571
189	2724096
190	2702081
191	2658072
192	2587433
193	2496377
194	2421374
195	2379554
196	2395348
197	2471050
198	2552034
199	2573911
200	2526733
201	2437095
202	2356929
203	2313876
204	2299408
205	2298144
206	2325223
207	2374544
208	2453729
209	2536533
210	2594963
211	2618266
212	2628346
213	2651888
214	2695145
215	2757422
216	2821750
217	2885658
218	2955348
219	3032922
220	3120814
221	3214371
222	3342509
223	3519440
224	3727920
225	3942670
226	4122110
227	4266511
228	4370180
229	4459107
230	4544669
231	4613803
232	4659047
233	4648752
234	4576725
235	4440591
236	4242513
237	3998062
238	3725469
239	3443261
240	3172307
241	2934961
242	2741220
243	2609290
244	2558109
245	2577296
246	2674102
247	2849074
248	3120258
249	3465971
250	3858167
251	4271713
252	4658031
253	4946501
254	5079773
255	5009401
256	4747826
257	4344146
258	3855134
259	3356625
260	2883549
261	2470905
262	2124517
263	1844781
264	1622392
265	1447714
266	1307632
267	1195499
268	1100059
269	1019739
270	949886
271	883427
272	825708
273	770874
274	718385
275	671612
276	625733
277	582880
278	544555
279	507230
280	472878
281	438188
282	406846
283	378309
284	350179
285	324002
286	298714
287	275043
288	252015
289	230737
290	210420
291	190688
292	172996
293	155943
294	139465
295	125095
296	111524
297	98792
298	87625
299	77270
300	68009
301	59394
302	52184
303	45062
304	39522
305	34121
306	29664
307	25846
308	22492
309	19389
310	16685
311	14650
312	12630
313	10793
314	9374
315	8350
316	7037
317	6201
318	5567
319	4768
320	4296
321	3698
322	3271
323	2932
324	2576
325	2342
326	2048
327	1735
328	1601
329	1380
330	1267
331	1042
332	907
333	848
334	747
335	627
336	522
337	477
338	420
339	343
340	308
341	270
342	259
343	210
344	178
345	126
346	133
347	115
348	98
349	82
350	83
351	63
352	65
353	44
354	53
355	48
356	28
357	36
358	27
359	27
360	27
361	23
362	23
363	12
364	19
365	11
366	11
367	19
368	15
369	16
370	10
371	7
372	9
373	16
374	7
375	10
376	9
377	8
378	6
379	3
380	8
381	1
382	7
383	5
384	6
385	7
386	4
387	5
388	4
389	1
390	4
391	7
392	4
393	3
394	4
395	4
396	4
397	5
398	2
399	3
400	3
401	5
403	5
404	5
405	2
406	3
407	2
408	2
410	1
411	2
412	2
414	1
415	2
417	2
418	3
419	1
420	3
424	5
425	4
426	1
428	2
429	1
432	2
433	3
434	1
435	1
436	3
437	3
438	1
439	3
444	1
446	2
447	1
448	1
450	1
453	2
454	1
455	1
459	1
463	1
464	1
465	1
467	3
470	1
471	1
473	1
475	1
476	1
477	2
479	1
483	1
487	1
488	1
490	1
495	1
497	2
499	1
502	2
508	1
510	1
516	1
518	1
519	1
522	1
527	1
529	1
532	1
533	1
534	1
535	3
539	1
543	1
559	1
565	1
574	1
575	1
578	1
581	2
583	1
587	1
592	1
594	1
596	2
599	2
600	1
603	2
604	1
606	1
607	1
609	1
611	1
612	2
614	1
615	3
617	1
618	1
620	1
622	2
623	1
624	1
628	1
630	2
631	2
632	2
634	1
640	3
643	2
644	3
645	3
646	1
647	1
648	1
649	4
651	2
653	1
654	1
655	2
656	1
660	3
664	2
666	1
668	1
669	1
670	1
671	1
674	2
675	1
676	1
678	1
683	1
707	1
711	1
714	1
715	1
728	1
766	2
770	1
809	1
908	1