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