1000
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 2 1
1 3 1
2 4 1
2 5 1
3 6 1
3 7 1
4 8 1
4 9 1
5 10 1
5 11 1
6 12 1
6 13 1
7 14 1
7 15 1
8 16 1
8 17 1
9 18 1
9 19 1
10 20 1
10 21 1
11 22 1
11 23 1
12 24 1
12 25 1
13 26 1
13 27 1
14 28 1
14 29 1
15 30 1
15 31 1
16 32 1
16 33 1
17 34 1
17 35 1
18 36 1
18 37 1
19 38 1
19 39 1
20 40 1
20 41 1
21 42 1
21 43 1
22 44 1
22 45 1
23 46 1
23 47 1
24 48 1
24 49 1
25 50 1
25 51 1
26 52 1
26 53 1
27 54 1
27 55 1
28 56 1
28 57 1
29 58 1
29 59 1
30 60 1
30 61 1
31 62 1
31 63 1
32 64 1
32 65 1
33 66 1
33 67 1
34 68 1
34 69 1
35 70 1
35 71 1
36 72 1
36 73 1
37 74 1
37 75 1
38 76 1
38 77 1
39 78 1
39 79 1
40 80 1
40 81 1
41 82 1
41 83 1
42 84 1
42 85 1
43 86 1
43 87 1
44 88 1
44 89 1
45 90 1
45 91 1
46 92 1
46 93 1
47 94 1
47 95 1
48 96 1
48 97 1
49 98 1
49 99 1
50 100 1
50 101 1
51 102 1
51 103 1
52 104 1
52 105 1
53 106 1
53 107 1
54 108 1
54 109 1
55 110 1
55 111 1
56 112 1
56 113 1
57 114 1
57 115 1
58 116 1
58 117 1
59 118 1
59 119 1
60 120 1
60 121 1
61 122 1
61 123 1
62 124 1
62 125 1
63 126 1
63 127 1
64 128 1
64 129 1
65 130 1
65 131 1
66 132 1
66 133 1
67 134 1
67 135 1
68 136 1
68 137 1
69 138 1
69 139 1
70 140 1
70 141 1
71 142 1
71 143 1
72 144 1
72 145 1
73 146 1
73 147 1
74 148 1
74 149 1
75 150 1
75 151 1
76 152 1
76 153 1
77 154 1
77 155 1
78 156 1
78 157 1
79 158 1
79 159 1
80 160 1
80 161 1
81 162 1
81 163 1
82 164 1
82 165 1
83 166 1
83 167 1
84 168 1
84 169 1
85 170 1
85 171 1
86 172 1
86 173 1
87 174 1
87 175 1
88 176 1
88 177 1
89 178 1
89 179 1
90 180 1
90 181 1
91 182 1
91 183 1
92 184 1
92 185 1
93 186 1
93 187 1
94 188 1
94 189 1
95 190 1
95 191 1
96 192 1
96 193 1
97 194 1
97 195 1
98 196 1
98 197 1
99 198 1
99 199 1
100 200 1
100 201 1
101 202 1
101 203 1
102 204 1
102 205 1
103 206 1
103 207 1
104 208 1
104 209 1
105 210 1
105 211 1
106 212 1
106 213 1
107 214 1
107 215 1
108 216 1
108 217 1
109 218 1
109 219 1
110 220 1
110 221 1
111 222 1
111 223 1
112 224 1
112 225 1
113 226 1
113 227 1
114 228 1
114 229 1
115 230 1
115 231 1
116 232 1
116 233 1
117 234 1
117 235 1
118 236 1
118 237 1
119 238 1
119 239 1
120 240 1
120 241 1
121 242 1
121 243 1
122 244 1
122 245 1
123 246 1
123 247 1
124 248 1
124 249 1
125 250 1
125 251 1
126 252 1
126 253 1
127 254 1
127 255 1
128 256 1
128 257 1
129 258 1
129 259 1
130 260 1
130 261 1
131 262 1
131 263 1
132 264 1
132 265 1
133 266 1
133 267 1
134 268 1
134 269 1
135 270 1
135 271 1
136 272 1
136 273 1
137 274 1
137 275 1
138 276 1
138 277 1
139 278 1
139 279 1
140 280 1
140 281 1
141 282 1
141 283 1
142 284 1
142 285 1
143 286 1
143 287 1
144 288 1
144 289 1
145 290 1
145 291 1
146 292 1
146 293 1
147 294 1
147 295 1
148 296 1
148 297 1
149 298 1
149 299 1
150 300 1
150 301 1
151 302 1
151 303 1
152 304 1
152 305 1
153 306 1
153 307 1
154 308 1
154 309 1
155 310 1
155 311 1
156 312 1
156 313 1
157 314 1
157 315 1
158 316 1
158 317 1
159 318 1
159 319 1
160 320 1
160 321 1
161 322 1
161 323 1
162 324 1
162 325 1
163 326 1
163 327 1
164 328 1
164 329 1
165 330 1
165 331 1
166 332 1
166 333 1
167 334 1
167 335 1
168 336 1
168 337 1
169 338 1
169 339 1
170 340 1
170 341 1
171 342 1
171 343 1
172 344 1
172 345 1
173 346 1
173 347 1
174 348 1
174 349 1
175 350 1
175 351 1
176 352 1
176 353 1
177 354 1
177 355 1
178 356 1
178 357 1
179 358 1
179 359 1
180 360 1
180 361 1
181 362 1
181 363 1
182 364 1
182 365 1
183 366 1
183 367 1
184 368 1
184 369 1
185 370 1
185 371 1
186 372 1
186 373 1
187 374 1
187 375 1
188 376 1
188 377 1
189 378 1
189 379 1
190 380 1
190 381 1
191 382 1
191 383 1
192 384 1
192 385 1
193 386 1
193 387 1
194 388 1
194 389 1
195 390 1
195 391 1
196 392 1
196 393 1
197 394 1
197 395 1
198 396 1
198 397 1
199 398 1
199 399 1
200 400 1
200 401 1
201 402 1
201 403 1
202 404 1
202 405 1
203 406 1
203 407 1
204 408 1
204 409 1
205 410 1
205 411 1
206 412 1
206 413 1
207 414 1
207 415 1
208 416 1
208 417 1
209 418 1
209 419 1
210 420 1
210 421 1
211 422 1
211 423 1
212 424 1
212 425 1
213 426 1
213 427 1
214 428 1
214 429 1
215 430 1
215 431 1
216 432 1
216 433 1
217 434 1
217 435 1
218 436 1
218 437 1
219 438 1
219 439 1
220 440 1
220 441 1
221 442 1
221 443 1
222 444 1
222 445 1
223 446 1
223 447 1
224 448 1
224 449 1
225 450 1
225 451 1
226 452 1
226 453 1
227 454 1
227 455 1
228 456 1
228 457 1
229 458 1
229 459 1
230 460 1
230 461 1
231 462 1
231 463 1
232 464 1
232 465 1
233 466 1
233 467 1
234 468 1
234 469 1
235 470 1
235 471 1
236 472 1
236 473 1
237 474 1
237 475 1
238 476 1
238 477 1
239 478 1
239 479 1
240 480 1
240 481 1
241 482 1
241 483 1
242 484 1
242 485 1
243 486 1
243 487 1
244 488 1
244 489 1
245 490 1
245 491 1
246 492 1
246 493 1
247 494 1
247 495 1
248 496 1
248 497 1
249 498 1
249 499 1
250 500 1
250 501 1
251 502 1
251 503 1
252 504 1
252 505 1
253 506 1
253 507 1
254 508 1
254 509 1
255 510 1
255 511 1
256 512 1
256 513 1
257 514 1
257 515 1
258 516 1
258 517 1
259 518 1
259 519 1
260 520 1
260 521 1
261 522 1
261 523 1
262 524 1
262 525 1
263 526 1
263 527 1
264 528 1
264 529 1
265 530 1
265 531 1
266 532 1
266 533 1
267 534 1
267 535 1
268 536 1
268 537 1
269 538 1
269 539 1
270 540 1
270 541 1
271 542 1
271 543 1
272 544 1
272 545 1
273 546 1
273 547 1
274 548 1
274 549 1
275 550 1
275 551 1
276 552 1
276 553 1
277 554 1
277 555 1
278 556 1
278 557 1
279 558 1
279 559 1
280 560 1
280 561 1
281 562 1
281 563 1
282 564 1
282 565 1
283 566 1
283 567 1
284 568 1
284 569 1
285 570 1
285 571 1
286 572 1
286 573 1
287 574 1
287 575 1
288 576 1
288 577 1
289 578 1
289 579 1
290 580 1
290 581 1
291 582 1
291 583 1
292 584 1
292 585 1
293 586 1
293 587 1
294 588 1
294 589 1
295 590 1
295 591 1
296 592 1
296 593 1
297 594 1
297 595 1
298 596 1
298 597 1
299 598 1
299 599 1
300 600 1
300 601 1
301 602 1
301 603 1
302 604 1
302 605 1
303 606 1
303 607 1
304 608 1
304 609 1
305 610 1
305 611 1
306 612 1
306 613 1
307 614 1
307 615 1
308 616 1
308 617 1
309 618 1
309 619 1
310 620 1
310 621 1
311 622 1
311 623 1
312 624 1
312 625 1
313 626 1
313 627 1
314 628 1
314 629 1
315 630 1
315 631 1
316 632 1
316 633 1
317 634 1
317 635 1
318 636 1
318 637 1
319 638 1
319 639 1
320 640 1
320 641 1
321 642 1
321 643 1
322 644 1
322 645 1
323 646 1
323 647 1
324 648 1
324 649 1
325 650 1
325 651 1
326 652 1
326 653 1
327 654 1
327 655 1
328 656 1
328 657 1
329 658 1
329 659 1
330 660 1
330 661 1
331 662 1
331 663 1
332 664 1
332 665 1
333 666 1
333 667 1
334 668 1
334 669 1
335 670 1
335 671 1
336 672 1
336 673 1
337 674 1
337 675 1
338 676 1
338 677 1
339 678 1
339 679 1
340 680 1
340 681 1
341 682 1
341 683 1
342 684 1
342 685 1
343 686 1
343 687 1
344 688 1
344 689 1
345 690 1
345 691 1
346 692 1
346 693 1
347 694 1
347 695 1
348 696 1
348 697 1
349 698 1
349 699 1
350 700 1
350 701 1
351 702 1
351 703 1
352 704 1
352 705 1
353 706 1
353 707 1
354 708 1
354 709 1
355 710 1
355 711 1
356 712 1
356 713 1
357 714 1
357 715 1
358 716 1
358 717 1
359 718 1
359 719 1
360 720 1
360 721 1
361 722 1
361 723 1
362 724 1
362 725 1
363 726 1
363 727 1
364 728 1
364 729 1
365 730 1
365 731 1
366 732 1
366 733 1
367 734 1
367 735 1
368 736 1
368 737 1
369 738 1
369 739 1
370 740 1
370 741 1
371 742 1
371 743 1
372 744 1
372 745 1
373 746 1
373 747 1
374 748 1
374 749 1
375 750 1
375 751 1
376 752 1
376 753 1
377 754 1
377 755 1
378 756 1
378 757 1
379 758 1
379 759 1
380 760 1
380 761 1
381 762 1
381 763 1
382 764 1
382 765 1
383 766 1
383 767 1
384 768 1
384 769 1
385 770 1
385 771 1
386 772 1
386 773 1
387 774 1
387 775 1
388 776 1
388 777 1
389 778 1
389 779 1
390 780 1
390 781 1
391 782 1
391 783 1
392 784 1
392 785 1
393 786 1
393 787 1
394 788 1
394 789 1
395 790 1
395 791 1
396 792 1
396 793 1
397 794 1
397 795 1
398 796 1
398 797 1
399 798 1
399 799 1
400 800 1
400 801 1
401 802 1
401 803 1
402 804 1
402 805 1
403 806 1
403 807 1
404 808 1
404 809 1
405 810 1
405 811 1
406 812 1
406 813 1
407 814 1
407 815 1
408 816 1
408 817 1
409 818 1
409 819 1
410 820 1
410 821 1
411 822 1
411 823 1
412 824 1
412 825 1
413 826 1
413 827 1
414 828 1
414 829 1
415 830 1
415 831 1
416 832 1
416 833 1
417 834 1
417 835 1
418 836 1
418 837 1
419 838 1
419 839 1
420 840 1
420 841 1
421 842 1
421 843 1
422 844 1
422 845 1
423 846 1
423 847 1
424 848 1
424 849 1
425 850 1
425 851 1
426 852 1
426 853 1
427 854 1
427 855 1
428 856 1
428 857 1
429 858 1
429 859 1
430 860 1
430 861 1
431 862 1
431 863 1
432 864 1
432 865 1
433 866 1
433 867 1
434 868 1
434 869 1
435 870 1
435 871 1
436 872 1
436 873 1
437 874 1
437 875 1
438 876 1
438 877 1
439 878 1
439 879 1
440 880 1
440 881 1
441 882 1
441 883 1
442 884 1
442 885 1
443 886 1
443 887 1
444 888 1
444 889 1
445 890 1
445 891 1
446 892 1
446 893 1
447 894 1
447 895 1
448 896 1
448 897 1
449 898 1
449 899 1
450 900 1
450 901 1
451 902 1
451 903 1
452 904 1
452 905 1
453 906 1
453 907 1
454 908 1
454 909 1
455 910 1
455 911 1
456 912 1
456 913 1
457 914 1
457 915 1
458 916 1
458 917 1
459 918 1
459 919 1
460 920 1
460 921 1
461 922 1
461 923 1
462 924 1
462 925 1
463 926 1
463 927 1
464 928 1
464 929 1
465 930 1
465 931 1
466 932 1
466 933 1
467 934 1
467 935 1
468 936 1
468 937 1
469 938 1
469 939 1
470 940 1
470 941 1
471 942 1
471 943 1
472 944 1
472 945 1
473 946 1
473 947 1
474 948 1
474 949 1
475 950 1
475 951 1
476 952 1
476 953 1
477 954 1
477 955 1
478 956 1
478 957 1
479 958 1
479 959 1
480 960 1
480 961 1
481 962 1
481 963 1
482 964 1
482 965 1
483 966 1
483 967 1
484 968 1
484 969 1
485 970 1
485 971 1
486 972 1
486 973 1
487 974 1
487 975 1
488 976 1
488 977 1
489 978 1
489 979 1
490 980 1
490 981 1
491 982 1
491 983 1
492 984 1
492 985 1
493 986 1
493 987 1
494 988 1
494 989 1
495 990 1
495 991 1
496 992 1
496 993 1
497 994 1
497 995 1
498 996 1
498 997 1
499 998 1
499 999 1
500 1000 1