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