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