0 0
1 1
2 20
3 11
4 300
5 210
6 120
7 111
8 4000
9 3100
10 2200
11 1300
12 2110
13 1210
14 1120
15 1111
16 50000
17 41000
18 32000
19 23000
20 14000
21 31100
22 22100
23 13100
24 21200
25 12200
26 11300
27 21110
28 12110
29 11210
30 11120
31 11111
32 600000
33 510000
34 420000
35 330000
36 240000
37 150000
38 411000
39 321000
40 231000
41 141000
42 312000
43 222000
44 132000
45 213000
46 123000
47 114000
48 311100
49 221100
50 131100
51 212100
52 122100
53 113100
54 211200
55 121200
56 112200
57 111300
58 211110
59 121110
60 112110
61 111210
62 111120
63 111111
64 7000000
65 6100000
66 5200000
67 4300000
68 3400000
69 2500000
70 1600000
71 5110000
72 4210000
73 3310000
74 2410000
75 1510000
76 4120000
77 3220000
78 2320000
79 1420000
80 3130000
81 2230000
82 1330000
83 2140000
84 1240000
85 1150000
86 4111000
87 3211000
88 2311000
89 1411000
90 3121000
91 2221000
92 1321000
93 2131000
94 1231000
95 1141000
96 3112000
97 2212000
98 1312000
99 2122000
100 1222000
101 1132000
102 2113000
103 1213000
104 1123000
105 1114000
106 3111100
107 2211100
108 1311100
109 2121100
110 1221100
111 1131100
112 2112100
113 1212100
114 1122100
115 1113100
116 2111200
117 1211200
118 1121200
119 1112200
120 1111300
121 2111110
122 1211110
123 1121110
124 1112110
125 1111210
126 1111120
127 1111111
128 80000000
129 71000000
130 62000000
131 53000000
132 44000000
133 35000000
134 26000000
135 17000000
136 61100000
137 52100000
138 43100000
139 34100000
140 25100000
141 16100000
142 51200000
143 42200000
144 33200000
145 24200000
146 15200000
147 41300000
148 32300000
149 23300000
150 14300000
151 31400000
152 22400000
153 13400000
154 21500000
155 12500000
156 11600000
157 51110000
158 42110000
159 33110000
160 24110000
161 15110000
162 41210000
163 32210000
164 23210000
165 14210000
166 31310000
167 22310000
168 13310000
169 21410000
170 12410000
171 11510000
172 41120000
173 32120000
174 23120000
175 14120000
176 31220000
177 22220000
178 13220000
179 21320000
180 12320000
181 11420000
182 31130000
183 22130000
184 13130000
185 21230000
186 12230000
187 11330000
188 21140000
189 12140000
190 11240000
191 11150000
192 41111000
193 32111000
194 23111000
195 14111000
196 31211000
197 22211000
198 13211000
199 21311000
200 12311000
201 11411000
202 31121000
203 22121000
204 13121000
205 21221000
206 12221000
207 11321000
208 21131000
209 12131000
210 11231000
211 11141000
212 31112000
213 22112000
214 13112000
215 21212000
216 12212000
217 11312000
218 21122000
219 12122000
220 11222000
221 11132000
222 21113000
223 12113000
224 11213000
225 11123000
226 11114000
227 31111100
228 22111100
229 13111100
230 21211100
231 12211100
232 11311100
233 21121100
234 12121100
235 11221100
236 11131100
237 21112100
238 12112100
239 11212100
240 11122100
241 11113100
242 21111200
243 12111200
244 11211200
245 11121200
246 11112200
247 11111300
248 21111110
249 12111110
250 11211110
251 11121110
252 11112110
253 11111210
254 11111120
255 11111111
256 900000000
257 810000000
258 720000000
259 630000000
260 540000000
261 450000000
262 360000000
263 270000000
264 180000000
265 711000000
266 621000000
267 531000000
268 441000000
269 351000000
270 261000000
271 171000000
272 612000000
273 522000000
274 432000000
275 342000000
276 252000000
277 162000000
278 513000000
279 423000000
280 333000000
281 243000000
282 153000000
283 414000000
284 324000000
285 234000000
286 144000000
287 315000000
288 225000000
289 135000000
290 216000000
291 126000000
292 117000000
293 611100000
294 521100000
295 431100000
296 341100000
297 251100000
298 161100000
299 512100000
300 422100000
301 332100000
302 242100000
303 152100000
304 413100000
305 323100000
306 233100000
307 143100000
308 314100000
309 224100000
310 134100000
311 215100000
312 125100000
313 116100000
314 511200000
315 421200000
316 331200000
317 241200000
318 151200000
319 412200000
320 322200000
321 232200000
322 142200000
323 313200000
324 223200000
325 133200000
326 214200000
327 124200000
328 115200000
329 411300000
330 321300000
331 231300000
332 141300000
333 312300000
334 222300000
335 132300000
336 213300000
337 123300000
338 114300000
339 311400000
340 221400000
341 131400000
342 212400000
343 122400000
344 113400000
345 211500000
346 121500000
347 112500000
348 111600000
349 511110000
350 421110000
351 331110000
352 241110000
353 151110000
354 412110000
355 322110000
356 232110000
357 142110000
358 313110000
359 223110000
360 133110000
361 214110000
362 124110000
363 115110000
364 411210000
365 321210000
366 231210000
367 141210000
368 312210000
369 222210000
370 132210000
371 213210000
372 123210000
373 114210000
374 311310000
375 221310000
376 131310000
377 212310000
378 122310000
379 113310000
380 211410000
381 121410000
382 112410000
383 111510000
384 411120000
385 321120000
386 231120000
387 141120000
388 312120000
389 222120000
390 132120000
391 213120000
392 123120000
393 114120000
394 311220000
395 221220000
396 131220000
397 212220000
398 122220000
399 113220000
400 211320000
401 121320000
402 112320000
403 111420000
404 311130000
405 221130000
406 131130000
407 212130000
408 122130000
409 113130000
410 211230000
411 121230000
412 112230000
413 111330000
414 211140000
415 121140000
416 112140000
417 111240000
418 111150000
419 411111000
420 321111000
421 231111000
422 141111000
423 312111000
424 222111000
425 132111000
426 213111000
427 123111000
428 114111000
429 311211000
430 221211000
431 131211000
432 212211000
433 122211000
434 113211000
435 211311000
436 121311000
437 112311000
438 111411000
439 311121000
440 221121000
441 131121000
442 212121000
443 122121000
444 113121000
445 211221000
446 121221000
447 112221000
448 111321000
449 211131000
450 121131000
451 112131000
452 111231000
453 111141000
454 311112000
455 221112000
456 131112000
457 212112000
458 122112000
459 113112000
460 211212000
461 121212000
462 112212000
463 111312000
464 211122000
465 121122000
466 112122000
467 111222000
468 111132000
469 211113000
470 121113000
471 112113000
472 111213000
473 111123000
474 111114000
475 311111100
476 221111100
477 131111100
478 212111100
479 122111100
480 113111100
481 211211100
482 121211100
483 112211100
484 111311100
485 211121100
486 121121100
487 112121100
488 111221100
489 111131100
490 211112100
491 121112100
492 112112100
493 111212100
494 111122100
495 111113100
496 211111200
497 121111200
498 112111200
499 111211200
500 111121200
501 111112200
502 111111300
503 211111110
504 121111110
505 112111110
506 111211110
507 111121110
508 111112110
509 111111210
510 111111120
511 111111111