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