0 1
1 1
2 1
3 2
4 2
5 3
6 3
7 4
8 5
9 5
10 6
11 7
12 8
13 8
14 10
15 10
16 11
17 12
18 12
19 14
20 13
21 15
22 15
23 16
24 17
25 17
26 19
27 19
28 21
29 21
30 23
31 24
32 25
33 27
34 27
35 30
36 30
37 32
38 33
39 34
40 36
41 36
42 38
43 38
44 40
45 40
46 41
47 42
48 42
49 44
50 43
51 45
52 45
53 46
54 47
55 47
56 49
57 49
58 51
59 51
60 53
61 54
62 55
63 57
64 57
65 60
66 60
67 62
68 63
69 64
70 66
71 66
72 68
73 68
74 70
75 70
76 71
77 72
78 72
79 74
80 73
81 75
82 75
83 76
84 77
85 77
86 79
87 79
88 81
89 81
90 83
91 84
92 85
93 87
94 87
95 90
96 90
97 92
98 93
99 94
100 96
101 96
102 98
103 98
104 100
105 100
106 101
107 102
108 102
109 104
110 103
111 105
112 105
113 106
114 107
115 107
116 109
117 109
118 111
119 111
120 113
121 114
122 115
123 117
124 117
125 120
126 120
127 122
128 123
129 124
130 126
131 126
132 128
133 128
134 130
135 130
136 131
137 132
138 132
139 134
140 133
141 135
142 135
143 136
144 137
145 137
146 139
147 139
148 141
149 141
150 143
151 144
152 145
153 147
154 147
155 150
156 150
157 152
158 153
159 154
160 156
161 156
162 158
163 158
164 160
165 160
166 161
167 162
168 162
169 164
170 163
171 165
172 165
173 166
174 167
175 167
176 169
177 169
178 171
179 171
180 173
181 174
182 175
183 177
184 177
185 180
186 180
187 182
188 183
189 184
190 186
191 186
192 188
193 188
194 190
195 190
196 191
197 192
198 192
199 194
200 193
201 195
202 195
203 196
204 197
205 197
206 199
207 199
208 201
209 201
210 203
211 204
212 205
213 207
214 207
215 210
216 210
217 212
218 213
219 214
220 216
221 216
222 218
223 218
224 220
225 220
226 221
227 222
228 222
229 224
230 223
231 225
232 225
233 226
234 227
235 227
236 229
237 229
238 231
239 231
240 233
241 234
242 235
243 237
244 237
245 240
246 240
247 242
248 243
249 244
250 246
251 246
252 248
253 248
254 250
255 250
256 251
257 252
258 252
259 254
260 253
261 255
262 255
263 256
264 257
265 257
266 259
267 259
268 261
269 261
270 263
271 264
272 265
273 267
274 267
275 270
276 270
277 272
278 273
279 274
280 276
281 276
282 278
283 278
284 280
285 280
286 281
287 282
288 282
289 284
290 283
291 285
292 285
293 286
294 287
295 287
296 289
297 289
298 291
299 291
300 293
301 294
302 295
303 297
304 297
305 300
306 300
307 302
308 303
309 304
310 306
311 306
312 308
313 308
314 310
315 310
316 311
317 312
318 312
319 314
320 313
321 315
322 315
323 316
324 317
325 317
326 319
327 319
328 321
329 321
330 323
331 324
332 325
333 327
334 327
335 330
336 330
337 332
338 333
339 334
340 336
341 336
342 338
343 338
344 340
345 340
346 341
347 342
348 342
349 344
350 343
351 345
352 345
353 346
354 347
355 347
356 349
357 349
358 351
359 351
360 353
361 354
362 355
363 357
364 357
365 360
366 360
367 362
368 363
369 364
370 366
371 366
372 368
373 368
374 370
375 370
376 371
377 372
378 372
379 374
380 373
381 375
382 375
383 376
384 377
385 377
386 379
387 379
388 381
389 381
390 383
391 384
392 385
393 387
394 387
395 390
396 390
397 392
398 393
399 394
400 396
401 396
402 398
403 398
404 400
405 400
406 401
407 402
408 402
409 404
410 403
411 405
412 405
413 406
414 407
415 407
416 409
417 409
418 411
419 411
420 413
421 414
422 415
423 417
424 417
425 420
426 420
427 422
428 423
429 424
430 426
431 426
432 428
433 428
434 430
435 430
436 431
437 432
438 432
439 434
440 433
441 435
442 435
443 436
444 437
445 437
446 439
447 439
448 441
449 441
450 443
451 444
452 445
453 447
454 447
455 450
456 450
457 452
458 453
459 454
460 456
461 456
462 458
463 458
464 460
465 460
466 461
467 462
468 462
469 464
470 463
471 465
472 465
473 466
474 467
475 467
476 469
477 469
478 471
479 471
480 473
481 474
482 475
483 477
484 477
485 480
486 480
487 482
488 483
489 484
490 486
491 486
492 488
493 488
494 490
495 490
496 491
497 492
498 492
499 494
500 493
501 495
502 495
503 496
504 497
505 497
506 499
507 499
508 501
509 501
510 503
511 504
512 505
513 507
514 507
515 510
516 510
517 512
518 513
519 514
520 516
521 516
522 518
523 518
524 520
525 520
526 521
527 522
528 522
529 524
530 523
531 525
532 525
533 526
534 527
535 527
536 529
537 529
538 531
539 531
540 533
541 534
542 535
543 537
544 537
545 540
546 540
547 542
548 543
549 544
550 546
551 546
552 548
553 548
554 550
555 550
556 551
557 552
558 552
559 554
560 553
561 555
562 555
563 556
564 557
565 557
566 559
567 559
568 561
569 561
570 563
571 564
572 565
573 567
574 567
575 570
576 570
577 572
578 573
579 574
580 576
581 576
582 578
583 578
584 580
585 580
586 581
587 582
588 582
589 584
590 583
591 585
592 585
593 586
594 587
595 587
596 589
597 589
598 591
599 591
600 593
601 594
602 595
603 597
604 597
605 600
606 600
607 602
608 603
609 604
610 606
611 606
612 608
613 608
614 610
615 610
616 611
617 612
618 612
619 614
620 613
621 615
622 615
623 616
624 617
625 617
626 619
627 619
628 621
629 621
630 623
631 624
632 625
633 627
634 627
635 630
636 630
637 632
638 633
639 634
640 636
641 636
642 638
643 638
644 640
645 640
646 641
647 642
648 642
649 644
650 643
651 645
652 645
653 646
654 647
655 647
656 649
657 649
658 651
659 651
660 653
661 654
662 655
663 657
664 657
665 660
666 660
667 662
668 663
669 664
670 666
671 666
672 668
673 668
674 670
675 670
676 671
677 672
678 672
679 674
680 673
681 675
682 675
683 676
684 677
685 677
686 679
687 679
688 681
689 681
690 683
691 684
692 685
693 687
694 687
695 690
696 690
697 692
698 693
699 694
700 696
701 696
702 698
703 698
704 700
705 700
706 701
707 702
708 702
709 704
710 703
711 705
712 705
713 706
714 707
715 707
716 709
717 709
718 711
719 711
720 713
721 714
722 715
723 717
724 717
725 720
726 720
727 722
728 723
729 724
730 726
731 726
732 728
733 728
734 730
735 730
736 731
737 732
738 732
739 734
740 733
741 735
742 735
743 736
744 737
745 737
746 739
747 739
748 741
749 741
750 743
751 744
752 745
753 747
754 747
755 750
756 750
757 752
758 753
759 754
760 756
761 756
762 758
763 758
764 760
765 760
766 761
767 762
768 762
769 764
770 763
771 765
772 765
773 766
774 767
775 767
776 769
777 769
778 771
779 771
780 773
781 774
782 775
783 777
784 777
785 780
786 780
787 782
788 783
789 784
790 786
791 786
792 788
793 788
794 790
795 790
796 791
797 792
798 792
799 794
800 793
801 795
802 795
803 796
804 797
805 797
806 799
807 799
808 801
809 801
810 803
811 804
812 805
813 807
814 807
815 810
816 810
817 812
818 813
819 814
820 816
821 816
822 818
823 818
824 820
825 820
826 821
827 822
828 822
829 824
830 823
831 825
832 825
833 826
834 827
835 827
836 829
837 829
838 831
839 831
840 833
841 834
842 835
843 837
844 837
845 840
846 840
847 842
848 843
849 844
850 846
851 846
852 848
853 848
854 850
855 850
856 851
857 852
858 852
859 854
860 853
861 855
862 855
863 856
864 857
865 857
866 859
867 859
868 861
869 861
870 863
871 864
872 865
873 867
874 867
875 870
876 870
877 872
878 873
879 874
880 876
881 876
882 878
883 878
884 880
885 880
886 881
887 882
888 882
889 884
890 883
891 885
892 885
893 886
894 887
895 887
896 889
897 889
898 891
899 891
900 893
901 894
902 895
903 897
904 897
905 900
906 900
907 902
908 903
909 904
910 906
911 906
912 908
913 908
914 910
915 910
916 911
917 912
918 912
919 914
920 913
921 915
922 915
923 916
924 917
925 917
926 919
927 919
928 921
929 921
930 923
931 924
932 925
933 927
934 927
935 930
936 930
937 932
938 933
939 934
940 936
941 936
942 938
943 938
944 940
945 940
946 941
947 942
948 942
949 944
950 943
951 945
952 945
953 946
954 947
955 947
956 949
957 949
958 951
959 951
960 953
961 954
962 955
963 957
964 957
965 960
966 960
967 962
968 963
969 964
970 966
971 966
972 968
973 968
974 970
975 970
976 971
977 972
978 972
979 974
980 973
981 975
982 975
983 976
984 977
985 977
986 979
987 979
988 981
989 981
990 983
991 984
992 985
993 987
994 987
995 990
996 990
997 992
998 993
999 994
1000 996
1001 996
1002 998
1003 998
1004 1000
1005 1000
1006 1001
1007 1002
1008 1002
1009 1004
1010 1003
1011 1005
1012 1005
1013 1006
1014 1007
1015 1007
1016 1009
1017 1009
1018 1011
1019 1011
1020 1013
1021 1014
1022 1015
1023 1017
1024 1017
1025 1020
1026 1020
1027 1022
1028 1023
1029 1024
1030 1026
1031 1026
1032 1028
1033 1028
1034 1030
1035 1030
1036 1031
1037 1032
1038 1032
1039 1034
1040 1033
1041 1035
1042 1035
1043 1036
1044 1037
1045 1037
1046 1039
1047 1039
1048 1041
1049 1041
1050 1043
1051 1044
1052 1045
1053 1047
1054 1047
1055 1050
1056 1050
1057 1052
1058 1053
1059 1054
1060 1056
1061 1056
1062 1058
1063 1058
1064 1060
1065 1060
1066 1061
1067 1062
1068 1062
1069 1064
1070 1063
1071 1065
1072 1065
1073 1066
1074 1067
1075 1067
1076 1069
1077 1069
1078 1071
1079 1071
1080 1073
1081 1074
1082 1075
1083 1077
1084 1077
1085 1080
1086 1080
1087 1082
1088 1083
1089 1084
1090 1086
1091 1086
1092 1088
1093 1088
1094 1090
1095 1090
1096 1091
1097 1092
1098 1092
1099 1094
1100 1093
1101 1095
1102 1095
1103 1096
1104 1097
1105 1097
1106 1099
1107 1099
1108 1101
1109 1101
1110 1103
1111 1104
1112 1105
1113 1107
1114 1107
1115 1110
1116 1110
1117 1112
1118 1113
1119 1114
1120 1116
1121 1116
1122 1118
1123 1118
1124 1120
1125 1120
1126 1121
1127 1122
1128 1122
1129 1124
1130 1123
1131 1125
1132 1125
1133 1126
1134 1127
1135 1127
1136 1129
1137 1129
1138 1131
1139 1131
1140 1133
1141 1134
1142 1135
1143 1137
1144 1137
1145 1140
1146 1140
1147 1142
1148 1143
1149 1144
1150 1146
1151 1146
1152 1148
1153 1148
1154 1150
1155 1150
1156 1151
1157 1152
1158 1152
1159 1154
1160 1153
1161 1155
1162 1155
1163 1156
1164 1157
1165 1157
1166 1159
1167 1159
1168 1161
1169 1161
1170 1163
1171 1164
1172 1165
1173 1167
1174 1167
1175 1170
1176 1170
1177 1172
1178 1173
1179 1174
1180 1176
1181 1176
1182 1178
1183 1178
1184 1180
1185 1180
1186 1181
1187 1182
1188 1182
1189 1184
1190 1183
1191 1185
1192 1185
1193 1186
1194 1187
1195 1187
1196 1189
1197 1189
1198 1191
1199 1191
1200 1193
1201 1194
1202 1195
1203 1197
1204 1197
1205 1200
1206 1200
1207 1202
1208 1203
1209 1204
1210 1206
1211 1206
1212 1208
1213 1208
1214 1210
1215 1210
1216 1211
1217 1212
1218 1212
1219 1214
1220 1213
1221 1215
1222 1215
1223 1216
1224 1217
1225 1217
1226 1219
1227 1219
1228 1221
1229 1221
1230 1223
1231 1224
1232 1225
1233 1227
1234 1227
1235 1230
1236 1230
1237 1232
1238 1233
1239 1234
1240 1236
1241 1236
1242 1238
1243 1238
1244 1240
1245 1240
1246 1241
1247 1242
1248 1242
1249 1244
1250 1243
1251 1245
1252 1245
1253 1246
1254 1247
1255 1247
1256 1249
1257 1249
1258 1251
1259 1251
1260 1253
1261 1254
1262 1255
1263 1257
1264 1257
1265 1260
1266 1260
1267 1262
1268 1263
1269 1264
1270 1266
1271 1266
1272 1268
1273 1268
1274 1270
1275 1270
1276 1271
1277 1272
1278 1272
1279 1274
1280 1273
1281 1275
1282 1275
1283 1276
1284 1277
1285 1277
1286 1279
1287 1279
1288 1281
1289 1281
1290 1283
1291 1284
1292 1285
1293 1287
1294 1287
1295 1290
1296 1290
1297 1292
1298 1293
1299 1294
1300 1296
1301 1296
1302 1298
1303 1298
1304 1300
1305 1300
1306 1301
1307 1302
1308 1302
1309 1304
1310 1303
1311 1305
1312 1305
1313 1306
1314 1307
1315 1307
1316 1309
1317 1309
1318 1311
1319 1311
1320 1313
1321 1314
1322 1315
1323 1317
1324 1317
1325 1320
1326 1320
1327 1322
1328 1323
1329 1324
1330 1326
1331 1326
1332 1328
1333 1328
1334 1330
1335 1330
1336 1331
1337 1332
1338 1332
1339 1334
1340 1333
1341 1335
1342 1335
1343 1336
1344 1337
1345 1337
1346 1339
1347 1339
1348 1341
1349 1341
1350 1343
1351 1344
1352 1345
1353 1347
1354 1347
1355 1350
1356 1350
1357 1352
1358 1353
1359 1354
1360 1356
1361 1356
1362 1358
1363 1358
1364 1360
1365 1360
1366 1361
1367 1362
1368 1362
1369 1364
1370 1363
1371 1365
1372 1365
1373 1366
1374 1367
1375 1367
1376 1369
1377 1369
1378 1371
1379 1371
1380 1373
1381 1374
1382 1375
1383 1377
1384 1377
1385 1380
1386 1380
1387 1382
1388 1383
1389 1384
1390 1386
1391 1386
1392 1388
1393 1388
1394 1390
1395 1390
1396 1391
1397 1392
1398 1392
1399 1394
1400 1393
1401 1395
1402 1395
1403 1396
1404 1397
1405 1397
1406 1399
1407 1399
1408 1401
1409 1401
1410 1403
1411 1404
1412 1405
1413 1407
1414 1407
1415 1410
1416 1410
1417 1412
1418 1413
1419 1414
1420 1416
1421 1416
1422 1418
1423 1418
1424 1420
1425 1420
1426 1421
1427 1422
1428 1422
1429 1424
1430 1423
1431 1425
1432 1425
1433 1426
1434 1427
1435 1427
1436 1429
1437 1429
1438 1431
1439 1431
1440 1433
1441 1434
1442 1435
1443 1437
1444 1437
1445 1440
1446 1440
1447 1442
1448 1443
1449 1444
1450 1446
1451 1446
1452 1448
1453 1448
1454 1450
1455 1450
1456 1451
1457 1452
1458 1452
1459 1454
1460 1453
1461 1455
1462 1455
1463 1456
1464 1457
1465 1457
1466 1459
1467 1459
1468 1461
1469 1461
1470 1463
1471 1464
1472 1465
1473 1467
1474 1467
1475 1470
1476 1470
1477 1472
1478 1473
1479 1474
1480 1476
1481 1476
1482 1478
1483 1478
1484 1480
1485 1480
1486 1481
1487 1482
1488 1482
1489 1484
1490 1483
1491 1485
1492 1485
1493 1486
1494 1487
1495 1487
1496 1489
1497 1489
1498 1491
1499 1491
1500 1493
1501 1494
1502 1495
1503 1497
1504 1497
1505 1500
1506 1500
1507 1502
1508 1503
1509 1504
1510 1506
1511 1506
1512 1508
1513 1508
1514 1510
1515 1510
1516 1511
1517 1512
1518 1512
1519 1514
1520 1513
1521 1515
1522 1515
1523 1516
1524 1517
1525 1517
1526 1519
1527 1519
1528 1521
1529 1521
1530 1523
1531 1524
1532 1525
1533 1527
1534 1527
1535 1530
1536 1530
1537 1532
1538 1533
1539 1534
1540 1536
1541 1536
1542 1538
1543 1538
1544 1540
1545 1540
1546 1541
1547 1542
1548 1542
1549 1544
1550 1543
1551 1545
1552 1545
1553 1546
1554 1547
1555 1547
1556 1549
1557 1549
1558 1551
1559 1551
1560 1553
1561 1554
1562 1555
1563 1557
1564 1557
1565 1560
1566 1560
1567 1562
1568 1563
1569 1564
1570 1566
1571 1566
1572 1568
1573 1568
1574 1570
1575 1570
1576 1571
1577 1572
1578 1572
1579 1574
1580 1573
1581 1575
1582 1575
1583 1576
1584 1577
1585 1577
1586 1579
1587 1579
1588 1581
1589 1581
1590 1583
1591 1584
1592 1585
1593 1587
1594 1587
1595 1590
1596 1590
1597 1592
1598 1593
1599 1594
1600 1596
1601 1596
1602 1598
1603 1598
1604 1600
1605 1600
1606 1601
1607 1602
1608 1602
1609 1604
1610 1603
1611 1605
1612 1605
1613 1606
1614 1607
1615 1607
1616 1609
1617 1609
1618 1611
1619 1611
1620 1613
1621 1614
1622 1615
1623 1617
1624 1617
1625 1620
1626 1620
1627 1622
1628 1623
1629 1624
1630 1626
1631 1626
1632 1628
1633 1628
1634 1630
1635 1630
1636 1631
1637 1632
1638 1632
1639 1634
1640 1633
1641 1635
1642 1635
1643 1636
1644 1637
1645 1637
1646 1639
1647 1639
1648 1641
1649 1641
1650 1643
1651 1644
1652 1645
1653 1647
1654 1647
1655 1650
1656 1650
1657 1652
1658 1653
1659 1654
1660 1656
1661 1656
1662 1658
1663 1658
1664 1660
1665 1660
1666 1661
1667 1662
1668 1662
1669 1664
1670 1663
1671 1665
1672 1665
1673 1666
1674 1667
1675 1667
1676 1669
1677 1669
1678 1671
1679 1671
1680 1673
1681 1674
1682 1675
1683 1677
1684 1677
1685 1680
1686 1680
1687 1682
1688 1683
1689 1684
1690 1686
1691 1686
1692 1688
1693 1688
1694 1690
1695 1690
1696 1691
1697 1692
1698 1692
1699 1694
1700 1693
1701 1695
1702 1695
1703 1696
1704 1697
1705 1697
1706 1699
1707 1699
1708 1701
1709 1701
1710 1703
1711 1704
1712 1705
1713 1707
1714 1707
1715 1710
1716 1710
1717 1712
1718 1713
1719 1714
1720 1716
1721 1716
1722 1718
1723 1718
1724 1720
1725 1720
1726 1721
1727 1722
1728 1722
1729 1724
1730 1723
1731 1725
1732 1725
1733 1726
1734 1727
1735 1727
1736 1729
1737 1729
1738 1731
1739 1731
1740 1733
1741 1734
1742 1735
1743 1737
1744 1737
1745 1740
1746 1740
1747 1742
1748 1743
1749 1744
1750 1746
1751 1746
1752 1748
1753 1748
1754 1750
1755 1750
1756 1751
1757 1752
1758 1752
1759 1754
1760 1753
1761 1755
1762 1755
1763 1756
1764 1757
1765 1757
1766 1759
1767 1759
1768 1761
1769 1761
1770 1763
1771 1764
1772 1765
1773 1767
1774 1767
1775 1770
1776 1770
1777 1772
1778 1773
1779 1774
1780 1776
1781 1776
1782 1778
1783 1778
1784 1780
1785 1780
1786 1781
1787 1782
1788 1782
1789 1784
1790 1783
1791 1785
1792 1785
1793 1786
1794 1787
1795 1787
1796 1789
1797 1789
1798 1791
1799 1791
1800 1793
1801 1794
1802 1795
1803 1797
1804 1797
1805 1800
1806 1800
1807 1802
1808 1803
1809 1804
1810 1806
1811 1806
1812 1808
1813 1808
1814 1810
1815 1810
1816 1811
1817 1812
1818 1812
1819 1814
1820 1813
1821 1815
1822 1815
1823 1816
1824 1817
1825 1817
1826 1819
1827 1819
1828 1821
1829 1821
1830 1823
1831 1824
1832 1825
1833 1827
1834 1827
1835 1830
1836 1830
1837 1832
1838 1833
1839 1834
1840 1836
1841 1836
1842 1838
1843 1838
1844 1840
1845 1840
1846 1841
1847 1842
1848 1842
1849 1844
1850 1843
1851 1845
1852 1845
1853 1846
1854 1847
1855 1847
1856 1849
1857 1849
1858 1851
1859 1851
1860 1853
1861 1854
1862 1855
1863 1857
1864 1857
1865 1860
1866 1860
1867 1862
1868 1863
1869 1864
1870 1866
1871 1866
1872 1868
1873 1868
1874 1870
1875 1870
1876 1871
1877 1872
1878 1872
1879 1874
1880 1873
1881 1875
1882 1875
1883 1876
1884 1877
1885 1877
1886 1879
1887 1879
1888 1881
1889 1881
1890 1883
1891 1884
1892 1885
1893 1887
1894 1887
1895 1890
1896 1890
1897 1892
1898 1893
1899 1894
1900 1896
1901 1896
1902 1898
1903 1898
1904 1900
1905 1900
1906 1901
1907 1902
1908 1902
1909 1904
1910 1903
1911 1905
1912 1905
1913 1906
1914 1907
1915 1907
1916 1909
1917 1909
1918 1911
1919 1911
1920 1913
1921 1914
1922 1915
1923 1917
1924 1917
1925 1920
1926 1920
1927 1922
1928 1923
1929 1924
1930 1926
1931 1926
1932 1928
1933 1928
1934 1930
1935 1930
1936 1931
1937 1932
1938 1932
1939 1934
1940 1933
1941 1935
1942 1935
1943 1936
1944 1937
1945 1937
1946 1939
1947 1939
1948 1941
1949 1941
1950 1943
1951 1944
1952 1945
1953 1947
1954 1947
1955 1950
1956 1950
1957 1952
1958 1953
1959 1954
1960 1956
1961 1956
1962 1958
1963 1958
1964 1960
1965 1960
1966 1961
1967 1962
1968 1962
1969 1964
1970 1963
1971 1965
1972 1965
1973 1966
1974 1967
1975 1967
1976 1969
1977 1969
1978 1971
1979 1971
1980 1973
1981 1974
1982 1975
1983 1977
1984 1977
1985 1980
1986 1980
1987 1982
1988 1983
1989 1984
1990 1986
1991 1986
1992 1988
1993 1988
1994 1990
1995 1990
1996 1991
1997 1992
1998 1992
1999 1994
2000 1993
2001 1995
2002 1995
2003 1996
2004 1997
2005 1997
2006 1999
2007 1999
2008 2001
2009 2001
2010 2003