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