8	1
9	10
10	56
11	222
12	720
13	2933
14	9272
15	55282
16	10448
17	3673
18	2103
19	14356
20	60193
21	20873
22	71318
23	31344
24	1000764
25	32394
26	365126
27	288625
28	334141
29	398573
30	304211
31	278826
32	266406
33	97535
34	50791
35	14696
36	33083
37	8852
38	3838
39	6174
40	2237
41	2632
42	5815
43	2118
44	1523
45	2736
46	2743
47	5430
48	15855
49	28793
50	7473
51	8839
52	2647
53	1308
54	2029
55	4237
56	9742
57	6535
58	9147
59	26805
60	63922
61	246805
62	512081
63	998365
64	1637842
65	1778700
66	1094326
67	667835
68	459291
69	355029
70	303316
71	269150
72	250773
73	261425
74	217042
75	191668
76	153523
77	135390
78	135926
79	159822
80	202704
81	224187
82	243852
83	251011
84	229607
85	205992
86	195171
87	190782
88	207133
89	221270
90	226887
91	241571
92	263612
93	291358
94	317251
95	288203
96	283124
97	293920
98	343975
99	447796
100	557308
101	673050
102	724983
103	709799
104	669354
105	688191
106	752891
107	787510
108	845506
109	885067
110	894411
111	869865
112	814862
113	756974
114	696261
115	617903
116	557984
117	476106
118	417574
119	379189
120	378471
121	378015
122	388910
123	457765
124	471515
125	515928
126	539017
127	516855
128	736755
129	672872
130	1436790
131	1176987
132	1968948
133	1550925
134	995113
135	987465
136	993832
137	963222
138	911829
139	871340
140	872422
141	838649
142	802849
143	789104
144	718238
145	779394
146	778589
147	793030
148	820000
149	802333
150	849369
151	762249
152	790774
153	779049
154	787312
155	793578
156	777243
157	909510
158	1884922
159	3640904
160	2342542
161	3584230
162	2353913
163	2049474
164	3536713
165	3522385
166	4194835
167	3388109
168	3144338
169	3193591
170	4394516
171	4356908
172	7754920
173	5793634
174	7567566
175	7486457
176	13640561
177	8180032
178	5290041
179	5406045
180	5129745
181	4218209
182	3679983
183	3654847
184	3356660
185	3010267
186	2974858
187	2965181
188	3409516
189	3526166
190	3232202
191	3287416
192	2873692
193	2547183
194	2297789
195	2073139
196	1916722
197	1808982
198	2149777
199	2274372
200	2727438
201	4683728
202	5607371
203	5668476
204	7007453
205	6005161
206	6418508
207	5910258
208	6357950
209	5802336
210	4860225
211	5442854
212	5415933
213	5143795
214	5144303
215	6873082
216	10843359
217	12236379
218	10625067
219	10321115
220	10216168
221	9553086
222	10102307
223	9900225
224	8056576
225	7746993
226	7276082
227	6230988
228	5382135
229	4709979
230	4436480
231	4249398
232	4112222
233	4458049
234	4301739
235	3901055
236	4216669
237	4789751
238	4315644
239	3658437
240	4105698
241	3558221
242	2807044
243	2449336
244	2072924
245	1931408
246	1828416
247	1595917
248	1508748
249	1666475
250	2076936
251	2588850
252	3596066
253	5149938
254	7421621
255	10702842
256	13060127
257	14829996
258	13425855
259	10101943
260	6594271
261	4490084
262	3207342
263	2421283
264	1848024
265	1461125
266	1160455
267	952053
268	803734
269	685199
270	600597
271	531571
272	466930
273	427237
274	394781
275	372225
276	351406
277	329239
278	315254
279	302760
280	292593
281	289473
282	267411
283	255335
284	243481
285	233630
286	222143
287	209999
288	197992
289	185185
290	176111
291	164733
292	154685
293	146666
294	140264
295	133036
296	125531
297	119031
298	112022
299	106110
300	101335
301	95765
302	90827
303	85733
304	80960
305	76716
306	72977
307	69593
308	67140
309	63843
310	62210
311	60344
312	58523
313	57294
314	55512
315	54603
316	52427
317	50913
318	49545
319	48134
320	46598
321	45847
322	44920
323	43628
324	42275
325	41167
326	39716
327	38817
328	37790
329	36511
330	35065
331	33691
332	32283
333	31085
334	30041
335	28535
336	27172
337	26045
338	24659
339	23144
340	22129
341	20473
342	19410
343	18152
344	16912
345	15302
346	14267
347	13474
348	12373
349	11552
350	10359
351	9741
352	8689
353	8150
354	7298
355	6592
356	5966
357	5441
358	4883
359	4383
360	3866
361	3510
362	3100
363	2705
364	2444
365	2160
366	1886
367	1768
368	1565
369	1400
370	1185
371	1032
372	900
373	771
374	673
375	558
376	561
377	459
378	404
379	363
380	320
381	292
382	246
383	205
384	190
385	150
386	135
387	123
388	91
389	77
390	88
391	67
392	68
393	47
394	47
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	4
413	1
414	3
415	3
416	1
417	1
418	5
419	2
420	1
423	1
427	1
428	1
430	2
435	1