8	1
9	10
10	56
11	222
12	722
13	2935
14	9271
15	55283
16	10449
17	3675
18	2102
19	14354
20	60199
21	20872
22	71319
23	31342
24	1000761
25	32389
26	365129
27	288624
28	334141
29	398571
30	304212
31	278826
32	266416
33	97541
34	50787
35	14697
36	33086
37	8855
38	3841
39	6176
40	2238
41	2632
42	5816
43	2118
44	1525
45	2736
46	2743
47	5431
48	15856
49	28796
50	7477
51	8841
52	2649
53	1310
54	2030
55	4237
56	9740
57	6536
58	9145
59	26807
60	63925
61	246801
62	512099
63	998375
64	1637878
65	1778695
66	1094343
67	667843
68	459294
69	355030
70	303328
71	269146
72	250779
73	261432
74	217056
75	191672
76	153530
77	135404
78	135931
79	159833
80	202720
81	224191
82	243861
83	251020
84	229615
85	206002
86	195186
87	190791
88	207148
89	221278
90	226894
91	241573
92	263619
93	291367
94	317266
95	288218
96	283141
97	293929
98	343987
99	447820
100	557333
101	673058
102	725000
103	709825
104	669379
105	688219
106	752909
107	787533
108	845524
109	885088
110	894434
111	869884
112	814882
113	757012
114	696288
115	617929
116	558006
117	476128
118	417594
119	379209
120	378495
121	378036
122	388934
123	457783
124	471540
125	515959
126	539045
127	516891
128	736793
129	672912
130	1436836
131	1177027
132	1968979
133	1550956
134	995156
135	987491
136	993877
137	963288
138	911862
139	871382
140	872466
141	838707
142	802909
143	789149
144	718279
145	779457
146	778630
147	793087
148	820042
149	802389
150	849415
151	762300
152	790833
153	779099
154	787361
155	793641
156	777321
157	909594
158	1885005
159	3641010
160	2342690
161	3584540
162	2354650
163	2050976
164	3539799
165	3527691
166	4203497
167	3400727
168	3160404
169	3211976
170	4414296
171	4377623
172	7775719
173	5814224
174	7587825
175	7506252
176	13660481
177	8199634
178	5309493
179	5424809
180	5148241
181	4236763
182	3698325
183	3672903
184	3374626
185	3027889
186	2992483
187	2982709
188	3427182
189	3543600
190	3249458
191	3304483
192	2890386
193	2563952
194	2314232
195	2089386
196	1933102
197	1825125
198	2165845
199	2290530
200	2743668
201	4699974
202	5624151
203	5684906
204	7023994
205	6021711
206	6435021
207	5926755
208	6374755
209	5819129
210	4876909
211	5459676
212	5432698
213	5160650
214	5161252
215	6890040
216	10860416
217	12253548
218	10642611
219	10338548
220	10233963
221	9570854
222	10120301
223	9918560
224	8074563
225	7765122
226	7294494
227	6249496
228	5400677
229	4728511
230	4455049
231	4268058
232	4131385
233	4476903
234	4320772
235	3920167
236	4235851
237	4809044
238	4334952
239	3678090
240	4125278
241	3578094
242	2827167
243	2469704
244	2093631
245	1952842
246	1850816
247	1620236
248	1537164
249	1706171
250	2137618
251	2692428
252	3755121
253	5361045
254	7667721
255	10981806
256	13365970
257	15160136
258	13766908
259	10429283
260	6902749
261	4786843
262	3502593
263	2720423
264	2148590
265	1764102
266	1467012
267	1262139
268	1116552
269	1002143
270	923165
271	859829
272	801219
273	766884
274	738035
275	716627
276	697666
277	671728
278	654098
279	636287
280	617770
281	606503
282	571392
283	545272
284	517749
285	490132
286	460384
287	429533
288	399434
289	368293
290	341740
291	312849
292	286950
293	261843
294	241949
295	221578
296	201290
297	184601
298	168210
299	153937
300	141517
301	129623
302	119078
303	109185
304	100590
305	92679
306	86096
307	80765
308	75981
309	71040
310	68290
311	65496
312	62736
313	60699
314	58249
315	56961
316	54419
317	52529
318	50996
319	49299
320	47628
321	46715
322	45649
323	44238
324	42860
325	41643
326	40119
327	39196
328	38129
329	36788
330	35339
331	33967
332	32518
333	31292
334	30256
335	28740
336	27312
337	26207
338	24837
339	23289
340	22237
341	20583
342	19507
343	18235
344	17017
345	15366
346	14359
347	13545
348	12452
349	11608
350	10436
351	9791
352	8724
353	8182
354	7336
355	6628
356	5988
357	5463
358	4901
359	4403
360	3884
361	3530
362	3106
363	2720
364	2458
365	2164
366	1897
367	1780
368	1578
369	1409
370	1191
371	1035
372	908
373	769
374	678
375	559
376	565
377	458
378	406
379	364
380	320
381	294
382	248
383	203
384	189
385	150
386	135
387	124
388	92
389	77
390	88
391	67
392	67
393	47
394	48
395	35
396	27
397	17
398	31
399	28
400	24
401	17
402	13
403	21
404	9
405	9
406	17
407	9
408	4
409	5
410	10
411	5
412	6
413	1
414	3
415	3
416	1
417	1
418	5
419	2
420	1
423	2
427	1
428	1
430	2
435	1