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