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

const long long MAX = 1000000000000000000;

long long MAP[18][10][10] = {
{{1,0,0,0,0,0,0,0,0,0},
{0,1,0,0,0,0,0,0,0,0},
{0,0,1,0,0,0,0,0,0,0},
{0,0,0,1,0,0,0,0,0,0},
{0,0,0,0,1,0,0,0,0,0},
{0,0,0,0,0,1,0,0,0,0},
{0,0,0,0,0,0,1,0,0,0},
{0,0,0,0,0,0,0,1,0,0},
{0,0,0,0,0,0,0,0,1,0},
{0,0,0,0,0,0,0,0,0,1}},

{{10,0,0,0,0,0,0,0,0,0},
{1,1,1,1,1,1,1,1,1,1},
{2,0,2,0,2,0,2,0,2,0},
{1,0,2,1,1,1,1,0,2,1},
{2,0,1,0,1,0,3,0,3,0},
{7,0,0,0,0,3,0,0,0,0},
{3,0,1,0,0,0,2,0,4,0},
{2,0,1,0,1,1,1,1,3,0},
{3,0,0,0,1,0,3,0,3,0},
{3,0,0,0,2,0,0,0,4,1}},

{{100,0,0,0,0,0,0,0,0,0},
{34,1,8,2,9,6,13,2,22,3},
{44,0,10,0,8,0,20,0,18,0},
{40,0,11,1,9,5,12,0,20,2},
{48,0,6,0,5,0,26,0,15,0},
{87,0,0,0,0,13,0,0,0,0},
{51,0,9,0,5,0,17,0,18,0},
{47,0,9,0,8,5,20,1,10,0},
{54,0,4,0,3,0,25,0,14,0},
{47,0,11,0,8,4,8,0,21,1}},

{{1000,0,0,0,0,0,0,0,0,0},
{552,1,68,3,55,33,141,3,138,6},
{632,0,58,0,33,0,162,0,115,0},
{613,0,79,1,39,21,105,0,139,3},
{681,0,39,0,16,0,157,0,107,0},
{958,0,0,0,0,42,0,0,0,0},
{694,0,61,0,18,0,107,0,120,0},
{694,0,42,0,28,21,160,1,54,0},
{755,0,32,0,6,0,124,0,83,0},
{684,0,87,0,19,15,61,0,133,1}},

{{10000,0,0,0,0,0,0,0,0,0},
{7263,1,466,4,214,132,1017,4,889,10},
{7913,0,353,0,98,0,920,0,716,0},
{7931,0,474,1,110,74,613,0,793,4},
{8431,0,256,0,37,0,716,0,560,0},
{9875,0,0,0,0,125,0,0,0,0},
{8480,0,324,0,42,0,551,0,603,0},
{8490,0,158,0,68,64,851,1,368,0},
{8853,0,204,0,10,0,549,0,384,0},
{8426,0,435,0,36,40,454,0,608,1}},

{{100000,0,0,0,0,0,0,0,0,0},
{85662,1,2670,5,615,435,5671,5,4921,15},
{89196,0,1897,0,230,0,4875,0,3802,0},
{89061,0,2301,1,245,245,4231,0,3911,5},
{91445,0,1356,0,71,0,4138,0,2990,0},
{99619,0,0,0,0,381,0,0,0,0},
{91008,0,1505,0,80,0,4376,0,3031,0},
{91302,0,615,0,135,245,4841,1,2861,0},
{92717,0,1055,0,15,0,3697,0,2516,0},
{90197,0,2061,0,60,160,4866,0,2655,1}},

{{1000000,0,0,0,0,0,0,0,0,0},
{920207,1,13460,6,1451,1466,36695,6,26687,21},
{933774,0,9528,0,462,0,34239,0,21997,0},
{929707,0,11421,1,471,951,37161,0,20282,6},
{942703,0,7026,0,181,0,30959,0,19131,0},
{998807,0,0,0,0,1193,0,0,0,0},
{938492,0,8066,0,255,0,36145,0,17042,0},
{944711,0,2723,0,356,1071,31657,1,19481,0},
{949299,0,5682,0,381,0,27476,0,17162,0},
{934209,0,11514,0,272,660,40587,0,12757,1}},

{{10000000,0,0,0,0,0,0,0,0,0},
{9491909,1,69420,7,3829,5341,274919,7,154539,28},
{9561834,0,52424,0,4088,0,249074,0,132580,0},
{9538181,0,65849,1,4599,3570,278572,0,109221,7},
{9618057,0,43660,0,8380,0,215859,0,114044,0},
{9996471,0,0,0,0,3529,0,0,0,0},
{9600907,0,53390,0,9030,0,243916,0,92757,0},
{9660218,0,20538,0,7203,3997,199990,1,108053,0},
{9666134,0,41076,0,15568,0,183288,0,93934,0},
{9594062,0,71365,0,7483,2219,259728,0,65142,1}},

{{100000000,0,0,0,0,0,0,0,0,0},
{96727773,1,417722,8,60180,18656,1905346,8,870270,36},
{97183454,0,365524,0,102076,0,1628882,0,720064,0},
{97126097,0,443468,1,92100,11516,1765044,0,561766,8},
{97570603,0,350312,0,153721,0,1354532,0,570832,0},
{99990575,0,0,0,0,9425,0,0,0,0},
{97548654,0,400655,0,136444,0,1460419,0,453828,0},
{97878586,0,253627,0,103832,12272,1241804,1,509878,0},
{97929955,0,346480,0,197436,0,1108366,0,417763,0},
{97622405,0,447454,0,93256,6160,1497504,0,333220,1}},

{{1000000000,0,0,0,0,0,0,0,0,0},
{979578102,1,3025242,9,939045,58029,11961897,9,4437621,45},
{982663764,0,2861164,0,1237482,0,9826356,0,3411234,0},
{982918871,0,3050403,1,974745,31869,10347712,0,2676390,9},
{985518393,0,2716767,0,1431757,0,7878618,0,2454465,0},
{999977349,0,0,0,0,22651,0,0,0,0},
{985857171,0,2737101,0,1135440,0,8275969,0,1994319,0},
{986865866,0,2468514,0,872481,32121,7594662,1,2166355,0},
{988296759,0,2465967,0,1451817,0,6168711,0,1616746,0},
{986706155,0,2547882,0,689718,14760,8430852,0,1610632,1}},

{{10000000000,0,0,0,0,0,0,0,0,0},
{9878382430,1,21873040,10,8732485,159430,70484777,10,20367762,55},
{9900526094,0,19875933,0,9375140,0,55772770,0,14450063,0},
{9904869365,0,18549872,1,6746485,77665,57999579,0,11757023,10},
{9921215165,0,17225847,0,8984341,0,42958482,0,9616165,0},
{9999950419,0,0,0,0,49581,0,0,0,0},
{9925270623,0,15470020,0,6592905,0,44579845,0,8086607,0},
{9925210327,0,17504924,0,5177200,74305,43064918,1,8968325,0},
{9939663569,0,13905250,0,7668415,0,32619365,0,6143401,0},
{9930928773,0,12496527,0,3684560,31620,45658394,0,7200125,1}},

{{100000000000,0,0,0,0,0,0,0,0,0},
{99326016765,1,136901413,11,56961531,392601,393138130,11,86589471,66},
{99474404786,0,114029719,0,52283957,0,300029554,0,59251984,0},
{99508935359,0,95437529,1,35198031,170951,309861453,0,50396665,11},
{99599615145,0,88964480,0,43316516,0,226544220,0,41559639,0},
{99999899712,0,0,0,0,100288,0,0,0,0},
{99629431515,0,72658872,0,29983250,0,231848266,0,36078097,0},
{99605068461,0,97084560,0,24155681,156101,225852154,1,47683042,0},
{99695226958,0,64420389,0,32267631,0,174572310,0,33512712,0},
{99660525302,0,52704410,0,15720617,62095,237397424,0,33590151,1}},

{{1000000000000,0,0,0,0,0,0,0,0,0},
{996499124003,1,722201372,12,289887214,882036,2099243511,12,388661761,78},
{997325950061,0,548127065,0,234585078,0,1585621052,0,305716744,0},
{997544339519,0,419808061,1,149913534,346710,1621936570,0,263655593,12},
{997934645314,0,388888545,0,172724905,0,1222418124,0,281323112,0},
{999999810115,0,0,0,0,189885,0,0,0,0},
{998128620262,0,292607074,0,114337410,0,1226533916,0,237901338,0},
{997878260436,0,446614093,0,94543912,303744,1191689622,1,388588192,0},
{998338308785,0,258797528,0,115887102,0,985390717,0,301615868,0},
{998299654938,0,194685645,0,57220132,113784,1249370002,0,198955498,1}},

{{10000000000000,0,0,0,0,0,0,0,0,0},
{9981948713433,1,3271729383,13,1229099287,1836159,11182203514,13,2366418106,91},
{9985836512869,0,2285533238,0,903400550,0,8637913830,0,2336639513,0},
{9987211394494,0,1619971288,1,559349921,657761,8723126763,0,1885499759,13},
{9988456300026,0,1508398229,0,629428255,0,6892012101,0,2513861389,0},
{9999999659867,0,0,0,0,340133,0,0,0,0},
{9989816998846,0,1047530068,0,417721980,0,6761320944,0,1956428162,0},
{9987751222276,0,1773930652,0,339754688,555373,6750044184,1,3384492826,0},
{9990122610763,0,962243490,0,459303364,0,5680583376,0,2775259007,0},
{9990887874782,0,644837349,0,218548824,197080,6864707499,0,1383834465,1}},

{{100000000000000,0,0,0,0,0,0,0,0,0},
{99902031287356,1,13114173697,14,4756606869,3586506,61491912211,14,18602433227,105},
{99919641710032,0,8606104340,0,3668907088,0,48528107058,0,19555171482,0},
{99929264352695,0,5647574611,1,2424698563,1180739,48266305206,0,14395888171,14},
{99931699651720,0,5483870016,0,3371107195,0,38898245701,0,20547125368,0},
{99999999418663,0,0,0,0,581337,0,0,0,0},
{99942017318716,0,3467777861,0,2569780759,0,37225384302,0,14719738362,0},
{99927873948748,0,6254904215,0,1614558232,964523,39307821385,1,24947802896,0},
{99939809553494,0,3566556644,0,4129671651,0,31435810812,0,21058407399,0},
{99949448192672,0,1963761996,0,1683101448,325780,37753002938,0,9151615165,1}},

{{1000000000000000,0,0,0,0,0,0,0,0,0},
{999441785434096,1,48104723380,15,24218431805,6638885,342906589613,15,142978182070,120},
{999530394990365,0,30615528854,0,27720348105,0,267931309640,0,143337823036,0},
{999601642329051,0,18366321393,1,21015375585,2023260,261504612384,0,97469338311,15},
{999593910499764,0,19811642068,0,38273670076,0,208454487722,0,139549700370,0},
{999999999045449,0,0,0,0,954551,0,0,0,0},
{999671553418406,0,11087644490,0,30658069785,0,193542768631,0,93158098688,0},
{999596377529707,0,19974463570,0,14620363805,1604205,217262336300,1,151763702412,0},
{999636863478955,0,13916789960,0,56183937930,0,161986434194,0,131049358961,0},
{999724777284070,0,5649374913,0,21235704485,517755,195567420696,0,52769698080,1}},

{{10000000000000000,0,0,0,0,0,0,0,0,0},
{9996797304009863,1,167526488628,16,233925901576,11738656,1849155959180,16,952075901928,136},
{9997280671340441,0,107723197271,0,331483705352,0,1393872382200,0,886249374736,0},
{9997801672282131,0,57668744012,1,250479263736,3332376,1325951950092,0,564224427636,16},
{9997619051982521,0,74116160124,0,468171031201,0,1042289009976,0,796371816178,0},
{9999999998485887,0,0,0,0,1514113,0,0,0,0},
{9998179884076364,0,35679377951,0,355983047880,0,927930426481,0,500523071324,0},
{9997909326894869,0,58643574930,0,156560419056,2571616,1094162376972,1,781304162556,0},
{9997832483391271,0,57128708096,0,630784474456,0,789834040308,0,689769385869,0},
{9998560580374487,0,15803521564,0,234139390192,795680,925632437780,0,263843480296,1}},

{{100000000000000000,0,0,0,0,0,0,0,0,0},
{99981980972837834,1,574289772576,17,2661527233449,19952441,9348828582989,17,5434361620523,153},
{99984541917142935,0,387158434419,0,3589960401658,0,6781742947852,0,4699221073136,0},
{99988218706190613,0,180552032329,1,2569422345249,5304425,6202558665292,0,2828755462074,17},
{99986225932168174,0,287637011553,0,4590583290265,0,4970554559287,0,3925292970721,0},
{99999999997669469,0,0,0,0,2330531,0,0,0,0},
{99990104052509256,0,118324717262,0,3289671369520,0,4145913647648,0,2342037756314,0},
{99989902464958499,0,160145819015,0,1426962514565,3993521,5009166641964,1,3501256072435,0},
{99987242858821151,0,236438712690,0,5518031810925,0,3833552629569,0,3169118025665,0},
{99992750965596212,0,44175064060,0,2039166442570,1187824,4001253338345,0,1164438370988,1}
}};

long long DEG16[100][10] =
{{10000000000000000,0,0,0,0,0,0,0,0,0},
{9996797304009863,1,167526488628,16,233925901576,11738656,1849155959180,16,952075901928,136},
{9997280671340441,0,107723197271,0,331483705352,0,1393872382200,0,886249374736,0},
{9997801672282131,0,57668744012,1,250479263736,3332376,1325951950092,0,564224427636,16},
{9997619051982521,0,74116160124,0,468171031201,0,1042289009976,0,796371816178,0},
{9999999998485887,0,0,0,0,1514113,0,0,0,0},
{9998179884076364,0,35679377951,0,355983047880,0,927930426481,0,500523071324,0},
{9997909326894869,0,58643574930,0,156560419056,2571616,1094162376972,1,781304162556,0},
{9997832483391271,0,57128708096,0,630784474456,0,789834040308,0,689769385869,0},
{9998560580374487,0,15803521564,0,234139390192,795680,925632437780,0,263843480296,1},
{10000000000000000,0,0,0,0,0,0,0,0,0},
{9994261945610933,1,892963347572,0,59454354254,2446200,4699681168004,0,85953073020,16},
{9998435783967383,0,23986901781,0,479845606496,0,631279381712,0,429104142628,0},
{9996583865270339,0,1028674347432,1,531029478832,458376,1493582512064,136,362847931124,1696},
{9998396352410331,0,30163814464,0,211174140057,0,762828092068,0,599481543080,0},
{9999999999634207,0,0,0,0,365793,0,0,0,0},
{9997950366458293,0,49090268244,0,796984668480,0,628495112015,0,575063492968,0},
{9995801501839084,0,1608162692296,0,1124163919000,152,716002643700,1,750168905751,16},
{9998847323516331,0,9270006488,0,315533727736,0,605214503092,0,222658246353,0},
{9998852192413575,0,210297156632,0,73528852376,146116,572826001676,136,291155429472,17},
{10000000000000000,0,0,0,0,0,0,0,0,0},
{9998695148143421,0,16743673425,0,151142490056,657120,735823586056,0,401141449922,0},
{9994782649202603,0,759465152960,0,31790429305,0,4373458159452,0,52637055680,0},
{9998214730940383,0,239769279280,0,41768228600,58096,1483463428913,0,20268064728,0},
{9998587445266527,0,18281639152,0,606793867696,0,432142761172,0,355336465453,0},
{9999999999936448,0,0,0,0,63552,0,0,0,0},
{9997320155691684,0,699272406113,0,747039349296,0,1031550780304,0,201981772603,0},
{9999110868929762,0,3118167956,0,175504951457,153456,618583618907,0,91924178462,0},
{9998753924702511,0,14399662504,0,270034311040,0,524925949893,0,436715374052,0},
{9998269089265517,0,6779542176,0,0,101360,1675482339946,0,48648751001,0},
{10000000000000000,0,0,0,0,0,0,0,0,0},
{9996400686404393,0,86812248974,1,27281734512,64208,3425054591448,0,60164956464,0},
{9998012127541779,0,44731235124,0,938956789680,0,543556341401,0,460628092016,0},
{9994855594034827,0,772333727412,0,77197848312,677040,4264811786712,0,30061925696,1},
{9996624260093327,0,1139208316649,0,1140647606080,0,566963417720,0,528920566224,0},
{9999999999687679,0,0,0,0,312321,0,0,0,0},
{9999034748857889,0,5902436528,0,399012541216,0,378031962810,0,182304201557,0},
{9996548230434575,16,1091974861661,0,270296,1681680,1240758881048,0,1119033870724,0},
{9999042457830389,0,267817063526,0,53660186192,0,433103149824,0,202961770069,0},
{9997696929574774,0,536570553152,0,663549847201,118356,853186251013,16,249763655368,120},
{10000000000000000,0,0,0,0,0,0,0,0,0},
{9997626800240683,0,795625374320,0,150976183601,0,1040591911552,0,386006289844,0},
{9999032419091851,0,8019522192,0,193510080416,0,472064344100,0,293986961441,0},
{9997932068270957,0,112812677729,0,136,1920,1735974771516,0,219144277742,0},
{9995304729745629,0,680443465164,0,13801100080,0,3969927432399,0,31098256728,0},
{9999999999925248,0,0,0,0,74752,0,0,0,0},
{9998551148539717,0,247500813852,0,17477888418,0,1169406519668,0,14466238345,0},
{9996047663535267,0,23455289960,0,10896,262200,1763430874141,0,2165450027536,0},
{9998664952974977,0,15525277114,0,717332637840,0,317915662725,0,284273447344,0},
{9998883270276594,0,22007942090,0,272,310368,573807928603,0,520913542073,0},
{10000000000000000,0,0,0,0,0,0,0,0,0},
{9996993118306365,0,1219524081310,0,943036067040,17,306885365948,0,537436179320,0},
{9997747431959048,0,444357307304,0,979558275712,0,727470434338,0,101182023598,0},
{9997779993539211,0,18240155212,240,7695856,10881,1881145797320,0,320612801280,0},
{9999321494757934,0,1659556056,0,221659860240,0,381334605556,0,73851220214,0},
{9999999999711712,0,0,0,0,288288,0,0,0,0},
{9998993459921822,0,6403564386,0,324590106516,0,370818492472,0,304727914804,0},
{9999365393342039,0,183064441640,0,20425768456,28057,312565128588,16,118551291204,0},
{9998638973104936,0,4026780884,0,0,0,1304110263956,0,52889850224,0},
{9998236991224361,0,75621809272,0,2732850120,11576,1502110234007,0,182543870664,0},
{10000000000000000,0,0,0,0,0,0,0,0,0},
{9999454858014507,0,27922900,0,784944,7280,402718196057,0,142395074312,0},
{9996614947772643,0,54113931885,0,14007313320,0,3284419242176,0,32511739976,0},
{9999238563829421,0,3764065024,0,119950967152,142096,474735871800,0,162985124507,0},
{9998058991607297,0,41013307942,0,1029842583120,0,515868990872,0,354283510769,0},
{9999999999985632,0,0,0,0,14368,0,0,0,0},
{9995425776194943,0,620224710264,0,38458603064,0,3898961056528,0,16579435201,0},
{9997195730508435,0,1324666155208,0,321116235440,0,791909638964,0,366577461953,0},
{9997326543904103,0,741453102876,0,1108586178960,0,473428460941,0,349988353120,0},
{9999103929768136,0,98717689312,0,25721055480,12320,760580339456,0,11051135296,0},
{10000000000000000,0,0,0,0,0,0,0,0,0},
{9999183735111719,0,31067123656,0,410213440,59484,337423647688,1,447363831412,12600},
{9999143031659185,0,4264712632,0,472746683137,0,234921228604,0,145035716442,0},
{9998250631444404,0,5468063920,0,572978003728,3636,1099507624048,0,71414860264,0},
{9996776579809739,0,1057313697800,0,41360,0,1100535590205,0,1065570860896,0},
{9999999999990559,0,0,0,0,9441,0,0,0,0},
{9999110713033987,0,358690003308,0,36686524000,0,362403627892,0,131506810813,0},
{9996441651717089,0,311268628934,0,66994543776,222784,3172771533448,0,7313353969,0},
{9998106258624880,0,334550628040,0,882984822720,0,544530291408,0,131675632952,0},
{9998205629406735,0,13769395496,0,3600,54080,1728727289848,136,51873850105,0},
{10000000000000000,0,0,0,0,0,0,0,0,0},
{9999494353745955,0,392597812,0,100618321440,21840,382799109796,0,21836203157,0},
{9998231299966433,0,584674065544,0,128995776256,0,703678608753,0,351351583014,0},
{9997209325449237,0,905048113016,0,9798896,1920,1737407791650,0,148208845281,0},
{9999264845017515,0,3509085236,0,233164540336,0,293398926733,0,205082430180,0},
{10000000000000000,0,0,0,0,0,0,0,0,0},
{9998295781781223,0,65069822100,0,16,0,1441043887061,0,198104509600,0},
{9998638138663450,0,1058746654,0,0,17880,1333771235720,0,27031336296,0},
{9995855161575143,0,629793852980,0,4597410800,0,3492802532316,0,17644628761,0},
{9999314652879393,0,111747809296,0,3315443977,240,564729337580,0,5554529514,0},
{10000000000000000,0,0,0,0,0,0,0,0,0},
{9997699875641553,0,391155125976,0,845286842672,47280,819547719108,0,244134623170,241},
{9998847325982679,0,248341322176,0,6035466768,0,888800259288,0,9496969089,0},
{9996475750146699,0,22254844112,0,8508820321,14740,3476546429752,0,16939744376,0},
{9996251460315483,0,20209090128,0,1920,0,1662977385836,0,2065353206633,0},
{9999999999989360,0,0,0,0,10640,0,0,0,0},
{9998704919873536,0,13860111124,0,792049811280,0,268883852940,0,220286351120,0},
{9998511768194779,0,12812566740,0,36063731376,0,1411526925000,0,27828582105,0},
{9999278548602061,0,10425677336,0,17,0,378395419178,0,332630301408,0},
{9995568083803435,0,619286171824,0,87293735240,152880,3713928595932,0,11407540689,0}};

long long DEG15[1000][10] =
{{1000000000000000,0,0,0,0,0,0,0,0,0},
{999441785434096,1,48104723380,15,24218431805,6638885,342906589613,15,142978182070,120},
{999530394990365,0,30615528854,0,27720348105,0,267931309640,0,143337823036,0},
{999601642329051,0,18366321393,1,21015375585,2023260,261504612384,0,97469338311,15},
{999593910499764,0,19811642068,0,38273670076,0,208454487722,0,139549700370,0},
{999999999045449,0,0,0,0,954551,0,0,0,0},
{999671553418406,0,11087644490,0,30658069785,0,193542768631,0,93158098688,0},
{999596377529707,0,19974463570,0,14620363805,1604205,217262336300,1,151763702412,0},
{999636863478955,0,13916789960,0,56183937930,0,161986434194,0,131049358961,0},
{999724777284070,0,5649374913,0,21235704485,517755,195567420696,0,52769698080,1},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999168901575061,1,147996088340,0,7318548660,1531635,648495467273,0,27286789015,15},
{999722656229965,0,6907309210,0,45644639265,0,138570753455,0,86221068105,0},
{999315993277160,0,238760478290,1,32572132755,309428,330919726930,120,81754073936,1380},
{999682389518315,0,11002777976,0,20717730571,0,158929986683,0,126959986455,0},
{999999999753954,0,0,0,0,246046,0,0,0,0},
{999662497948227,0,11147593903,0,80263703520,0,127795276816,0,118295477534,0},
{999252130781474,0,296674648158,0,137619023220,135,156253029997,1,157322517000,15},
{999780405256444,0,3233910810,0,32021606100,0,136661365059,0,47677861587,0},
{999753628360293,0,22405194228,0,20438063640,104525,135656700008,120,67871577170,16},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999727411154567,0,6364922911,0,15654953280,438375,161887883932,0,88680646935,0},
{999238231448049,0,119287000440,0,4606737466,0,620110627735,0,17764186310,0},
{999630158268677,0,38288094292,0,10072167275,42435,318096155106,0,3385272215,0},
{999756282234273,0,4776600135,0,65217877740,0,96750138740,0,76973149112,0},
{999999999954715,0,0,0,0,45285,0,0,0,0},
{999486876964153,0,178310326111,0,51637050675,0,233843512466,0,49332146595,0},
{999816944621401,0,1282660150,0,19031037496,106940,141467007195,0,21274566818,0},
{999751645624105,0,5617289165,0,29260689315,0,113321122657,0,100155274758,0},
{999670183698169,0,2371375081,0,0,73710,319874562228,0,7570290812,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999533571030833,0,27249660428,1,9639484885,47103,410032778030,0,19506998720,0},
{999674935694062,0,10025850345,0,107573466000,0,105152224951,0,102312764642,0},
{999225127806973,0,138968835631,0,11396858560,453180,614209326200,0,10296719455,1},
{999377646693056,0,229874328976,0,154226351125,0,120324511525,0,117928115318,0},
{999999999785244,0,0,0,0,214756,0,0,0,0},
{999820260273170,0,1913085338,0,45753047355,0,90258571441,0,41815022696,0},
{999498760256997,15,167376326671,0,194160,780780,211740346914,0,122122094463,0},
{999814980577657,0,21987013416,0,16083318645,0,95862944180,0,51086146102,0},
{999553436310022,0,135351059605,0,47197640701,85170,206403391629,15,57611512753,105},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999542414319213,0,157823392890,0,11198311636,0,210862778486,0,77701197775,0},
{999793769285561,0,3257360905,0,22248940365,0,110256113028,0,70468300141,0},
{999667793502015,0,20475702549,0,120,1575,269276248591,0,42454545150,0},
{999297315309882,0,103667469395,0,2338051200,0,585549788053,0,11129381470,0},
{999999999946525,0,0,0,0,53475,0,0,0,0},
{999685729728739,0,39865026440,0,4702971975,0,267285109465,0,2417163381,0},
{999435656036155,0,4948941040,0,8415,173460,250614142727,0,308780698203,0},
{999774584326408,0,3823725390,0,87298020810,0,68162976262,0,66130951130,0},
{999727779823289,0,8166264255,0,240,213150,136802051205,0,127251647861,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999431059469948,0,238857698188,0,137506917240,16,72380742580,0,120195172028,0},
{999607792836898,0,123917073133,0,77356805541,0,164056188733,0,26877095695,0},
{999678209579467,0,6379527995,210,535200,8401,247362729894,0,68047618833,0},
{999860373052137,0,679741673,0,27140846460,0,93727739865,0,18078619865,0},
{999999999800710,0,0,0,0,199290,0,0,0,0},
{999802265883929,0,2665351253,0,39424029645,0,80541662695,0,75103072478,0},
{999866066667826,0,18496741720,0,6360390870,21471,77830139790,15,31246038308,0},
{999748934034860,0,1464154150,0,0,0,243804184260,0,5797626730,0},
{999639193889369,0,22362145275,0,601260660,8975,285293670100,0,52549025621,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999873893445591,0,16306255,0,518940,5460,105350111786,0,20739611968,0},
{999561448159372,0,17817052306,0,5350430085,0,404350834542,0,11033523695,0},
{999827688290152,0,1595144895,0,14633711835,101130,115161220472,0,40921531516,0},
{999679811226503,0,9515217105,0,133686382830,0,92556458175,0,84430715387,0},
{999999999989297,0,0,0,0,10703,0,0,0,0},
{999290289872521,0,110495233250,0,6572452608,0,586601927210,0,6040514411,0},
{999508099897096,0,166076869380,0,73663394805,0,168246703133,0,83913135586,0},
{999491075632295,0,163870275600,0,165688291860,0,96287238925,0,83078561320,0},
{999791660400332,0,16941942165,0,7023326415,9555,182681580503,0,1692741030,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999829923599068,0,10272761535,0,158143440,42645,62539518096,1,97105925660,9555},
{999845242598914,0,1257580005,0,61137055981,0,56888868475,0,35473896625,0},
{999717017441188,0,2116298104,0,77055731025,2850,182619418610,0,21191108223,0},
{999516931135603,0,166968563415,0,31815,0,188978429932,0,127121839235,0},
{999999999992754,0,0,0,0,7246,0,0,0,0},
{999851761828441,0,28583648410,0,11832154425,0,72038433603,0,35783935121,0},
{999395918076147,0,53080859606,0,11150940885,152895,537200414673,0,2649555794,0},
{999664413506742,0,93077423460,0,72829326570,0,136437574735,0,33242168493,0},
{999750705162429,0,2874122840,0,2940,38355,230196361740,120,16224311576,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999884889051674,0,192023780,0,13186380480,16380,95900244577,0,5832283109,0},
{999634002520411,0,127855897743,0,11691383110,0,152663522241,0,73786676495,0},
{999498484014308,0,144686071490,0,5944590,1575,312700966731,0,44123001306,0},
{999844315693641,0,1522503153,0,29990350390,0,71243522131,0,52927930685,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999709002729898,0,13220916660,0,15,0,240455702311,0,37320651116,0},
{999763636311642,0,443515445,0,0,13860,231910643988,0,4009515065,0},
{999354248509011,0,96927307680,0,908048535,0,541227822910,0,6688311864,0},
{999836867879168,0,24438336981,0,1312311786,210,136728680825,0,652791030,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999568564204856,0,106633003238,0,79997968290,34335,185119795926,0,59684993144,211},
{999738585826811,0,41446748960,0,1809563730,0,216488037938,0,1669822561,0},
{999522673945249,0,7800283640,0,3298555261,11445,460082053490,0,6145150915,0},
{999461276113724,0,4209425340,0,1575,0,233870380390,0,300644078971,0},
{999999999991810,0,0,0,0,8190,0,0,0,0},
{999781763731807,0,3422092405,0,108643209675,0,51625015818,0,54545950295,0},
{999675590367064,0,4433956935,0,10476077720,0,299846011530,0,9653586751,0},
{999811559668331,0,4137289435,0,16,0,95457824370,0,88845217848,0},
{999291913212579,0,122540553230,0,15162716340,109200,566285793950,0,4097614701,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999781892154197,0,6147781185,0,264360635,0,158846775765,0,52848928218,0},
{999537514804522,0,177911940615,0,143774532840,0,51570581808,0,89228140215,0},
{999765568439894,0,155325565055,0,274614810,0,43689016395,0,35142363846,0},
{999680739282350,0,80018118945,0,108050747805,0,117956578125,0,13235272775,0},
{999999999950635,0,0,0,0,49365,0,0,0,0},
{999716549119602,0,2441466538,0,479130,0,238785994455,0,42222940275,0},
{999693697374660,0,20483324830,0,169132005,470,257339600895,0,28310567140,0},
{999890678879205,0,364006145,0,36161405280,0,57779535390,0,15016173980,0},
{999839474405409,0,18339485635,0,85290,0,110480402040,0,31705621626,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999590548061145,1,119566740785,0,16920,225225,143269620780,0,146615335144,0},
{999835461648786,0,1186764661,0,49811541780,0,59438771413,0,54101273360,0},
{999776206593539,0,1034880,1,19320,21945,154041054115,0,69751276200,0},
{999897461509054,0,21369435250,0,4785255931,0,53979982550,0,22403817215,0},
{999999999995574,0,0,0,0,4426,0,0,0,0},
{999810647030789,0,904092191,0,0,0,182134577302,0,6314299718,0},
{999706048898861,0,72606864650,0,61387806495,18740,118845743520,1,41110667733,0},
{999736428404695,0,15012432645,0,561470910,0,215833398918,0,32164292832,0},
{999528756960364,0,216694300305,0,105180480420,0,107112127200,0,42256131710,1},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999685652293367,0,32105791,0,17798235,0,208561286417,0,105736516190,0},
{999911747353493,0,5247860,0,162646,0,73922291399,0,14324944602,0},
{999667871602161,0,122870126940,0,20927246460,0,151554776021,0,36776248418,0},
{999584007260134,0,11051788205,0,2709546840,0,396318440220,0,5912964601,0},
{999999999999335,0,0,0,0,665,0,0,0,0},
{999874945087663,0,774477916,0,19720857975,0,73639089091,0,30920487355,0},
{999309682060223,0,201224729165,0,145385340706,5670,341269505001,0,2438359235,0},
{999683298379794,0,9010286040,0,153594395955,0,87914709811,0,66182228400,0},
{999716387686055,0,19297484535,0,0,210,236825431436,0,27489397764,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999827953637497,0,80368023778,1,1926197028,10220,87816824390,0,1935307086,0},
{999354560866166,0,91067519085,0,3073853840,0,547848068886,0,3449692023,0},
{999868868921070,0,42330695533,0,4595564185,8855,35331434330,0,48873376026,1},
{999590285187333,0,177813645911,0,47428886505,0,113363507885,0,71108772366,0},
{999999999990339,0,0,0,0,9661,0,0,0,0},
{999588710689603,0,106941889735,0,169080584400,0,80594016570,0,54672819692,0},
{999637247387485,0,20641547804,0,55517889015,0,235508743676,0,51084432020,0},
{999835155158108,0,17601576090,0,3099546450,0,142851449990,0,1292269362,0},
{999778963642185,0,85396424465,0,11985205066,665,55405173645,0,68249553974,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999510027806887,0,951352220,0,1,46410,220869870857,0,268150923625,0},
{999861468195224,0,6533272740,0,95255160,0,50539847940,0,81363428936,0},
{999898227587165,0,1751106751,0,16172636565,32775,26560348460,0,57288288284,0},
{999858013502706,0,958738395,0,76113947910,0,35849678769,0,29064132220,0},
{999999999989570,0,0,0,0,10430,0,0,0,0},
{999759476150289,0,832985605,0,63614864040,0,165892453850,0,10183546216,0},
{999850797531104,0,2302451415,0,15,49140,81606584416,0,65293383910,0},
{999541847799099,0,161740074825,0,4725,0,170923006606,0,125489114745,0},
{999725261265926,0,83528001510,0,0,1365,180519300853,0,10691430346,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999778232192542,0,1354402030,0,3797495,1711,218066284650,0,2343321572,0},
{999867376472895,0,40954766000,0,8113609140,0,60422962460,0,23132189505,0},
{999594606807822,0,177337610719,0,111087737895,1,31480395095,0,85487448468,0},
{999472607338845,0,48684616755,0,5962051530,0,471092374425,0,1653618445,0},
{999999999999775,0,0,0,0,225,0,0,0,0},
{999730631649615,0,59740356936,0,103716112500,0,89028815216,0,16883065733,0},
{999766612556524,0,47734731900,0,31674881295,1,153110851965,0,866978315,0},
{999769863129035,0,2670247560,0,210,0,217966858765,0,9499764430,0},
{999696612954419,0,2685931760,15,245700,1590,236467039695,0,64233826821,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999845987143445,0,38098278198,0,10441791585,0,97604505047,0,7868281725,0},
{999917404866092,0,88466206,0,17484960675,0,60409655002,0,4612052025,0},
{999628745736988,0,194000182005,0,300525,4305,163937056405,0,13316719772,0},
{999721144620799,0,94852410135,0,10403127750,0,105279855035,0,68319986281,0},
{999999999948130,0,0,0,0,51870,0,0,0,0},
{999582021466249,0,132756300470,0,1699425,0,259067150960,0,26153382896,0},
{999761258995989,0,9734364900,0,7258680,1575,132371870940,0,96627507916,0},
{999878773984709,0,645571500,0,37924616730,0,44752844201,0,37902982860,0},
{999636915473841,0,100298945595,0,115650,0,168808283170,0,93977181744,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999932048084529,0,14169662075,0,1320495540,3075,41703404755,1,10758350025,0},
{999753630485028,0,7760106530,0,1,0,202826329396,0,35783079045,0},
{999707339499179,0,552591141,0,27134600235,120,254286174695,0,10687134630,0},
{999816105974064,0,195365510,0,0,0,180300605571,0,3398054855,0},
{999999999990324,0,0,0,0,9676,0,0,0,0},
{999415225607494,0,94676257420,0,239872845,0,486028731045,0,3829531196,0},
{999756867682259,0,7276493280,0,0,1710,211365784160,0,24490038591,0},
{999894107345986,0,15042988085,0,410089800,0,90075749944,0,363826185,0},
{999679293452935,0,147359979055,0,107655,0,152506710389,0,20839749966,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999887260973783,0,51433453190,0,1643460,0,61023751646,0,280177921,0},
{999660278157039,0,71670976315,0,105698032455,0,128807130261,0,33545703930,0},
{999945999709809,0,1973750,0,36975,0,36061911345,0,17936368121,0},
{999788362978613,0,42144176495,0,543730110,0,167884823704,0,1064291078,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999543315432279,0,4842572820,0,1749187440,0,446845537441,0,3247270020,0},
{999688606398145,0,150749675135,0,26020809585,15,83291210040,0,51331907080,0},
{999493537015414,0,3659455815,0,210,0,214619693870,0,288183834691,0},
{999897447165389,0,281240730,0,10969059466,19110,77276328785,0,14026186520,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999907118933858,0,1184352458,0,683214315,665,28878933108,0,62134565595,1},
{999783514133935,0,3187220520,0,125480024670,0,44721979219,0,43096641656,0},
{999783615463873,0,234833385,0,951827896,30,215067532325,0,130342491,0},
{999763599936502,0,2247135534,0,4412659800,0,225894717368,0,3845550796,0},
{999999999997030,0,0,0,0,2970,0,0,0,0},
{999877420977532,0,1915182405,0,0,0,64129394198,0,56534445865,0},
{999479513878829,0,48019501985,0,56035995,3500,323221433630,0,149189146061,0},
{999360170250635,0,94659748935,0,8089361281,0,534998819188,0,2081819961,0},
{999887402432431,0,119018460,0,38769298260,785,36613625025,0,37095625039,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999609150301332,0,170150742545,0,60027732765,0,120964242413,0,39706980945,0},
{999753611248940,0,5607416010,0,296639295,0,168186293570,0,72298402185,0},
{999778286254063,0,727205575,0,0,1575,209058844844,0,11927693943,0},
{999631695785307,0,121531150905,0,144530282715,0,39995593220,0,62247187853,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999785554727405,0,167657462835,0,66403155,0,27716152200,0,19005254405,0},
{999899091440084,0,5383436640,0,4075131060,1680,90571767160,0,878223376,0},
{999717470595363,0,47858172825,0,139532232840,0,89054607411,0,6084391561,0},
{999566794745953,0,141143648625,0,14200515435,0,104065873671,0,173795216316,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999812080788000,0,268347290,0,5120340,0,157949643725,0,29696100645,0},
{999745275489966,0,798681135,0,1448371,0,230132904658,0,23791475870,0},
{999917569680340,0,2338745495,0,0,12068,35328572782,0,44762987950,1365},
{999733611399311,0,18407881170,0,45466100,0,221449454912,0,26485798507,0},
{999999999999880,0,0,0,0,120,0,0,0,0},
{999909270753775,0,210110802,0,44979114180,0,33391259688,0,12148761555,0},
{999514165178416,0,9936131201,0,2433661231,3165,463589493834,0,9875532153,0},
{999866732866142,0,13644267170,0,11565,0,92849749060,0,26773106063,0},
{999755586438888,0,699804246,0,98984095665,665,132511146460,0,12218514076,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999897457377784,0,12225414505,0,2655252601,0,87186839890,0,475115220,0},
{999606389954368,0,121706698380,0,2255,0,126406157281,0,145497187716,0},
{999915953172001,0,4725900229,0,782431875,15,78005687470,0,532808410,0},
{999855344616517,0,505504394,0,58684799355,0,47619727678,0,37845352056,0},
{999999999999320,0,0,0,0,680,0,0,0,0},
{999824125302395,0,96915,0,1575,0,115661592958,0,60213006157,0},
{999661234756174,0,111858343995,0,120457447110,16395,68526176136,0,37923260190,0},
{999911524086922,0,28812672945,0,3371877915,0,41324849479,0,14966512739,0},
{999741679698516,0,90013451010,0,139335,0,128174564013,0,40132147126,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999533224837356,0,36221619610,0,14474565540,42315,415707134949,0,371800230,0},
{999856758962189,0,548687088,0,0,0,134954279213,0,7738071510,0},
{999658880773139,0,33773401280,0,14813939130,0,272823838080,0,19708048371,0},
{999771952699524,0,44679958388,0,88219040910,0,72366373357,0,22781927821,0},
{999999999967225,0,0,0,0,32775,0,0,0,0},
{999814609488153,0,9657913545,0,489338850,0,157105375875,0,18137883577,0},
{999758281192526,0,644759550,0,210,11193,235123014860,15,5951021646,0},
{999646128327009,0,148348622010,0,92133427530,0,87570796281,0,25818827170,0},
{999734451703432,0,77412374320,0,574247145,1470,179660046238,105,7901627290,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999787063285070,0,3826383590,0,11403,19110,180010290036,0,29100010791,0},
{999758505926666,0,19984810,0,8396115,0,160998456034,0,80467236375,0},
{999933860549750,0,19918470,0,6552147420,1365,58631848405,0,935534590,0},
{999933060121260,0,1766865,0,44100,0,52707598855,0,14230468920,0},
{999999999971047,0,0,0,0,28953,0,0,0,0},
{999749835839296,0,94308588675,0,19494111225,0,102281129179,0,34080331625,0},
{999540851290979,0,38949264826,0,121182626565,1575,285992904385,0,13023911670,0},
{999606549605647,0,6530634968,0,1243602360,0,382689486735,0,2986670290,0},
{999643279555329,0,83174657045,0,1184821,210,250264841572,0,23279761023,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999716604473234,0,180401288340,0,38047829820,455,61711943631,0,3234464520,0},
{999908696273292,0,341495973,0,24938283825,0,43878904920,0,22145041990,0},
{999643246252016,0,14807730,0,2734095,15,177208184264,0,179528021880,0},
{999349063396157,0,201922102540,0,142016566632,0,304384949866,0,2612984805,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999690486365117,0,8245999350,0,163058712180,0,89000492753,0,49208430600,0},
{999748954212861,0,93054418641,0,9555,0,90595371978,0,67395986965,0},
{999760193297849,0,11036791185,0,0,0,205826068580,0,22943842386,0},
{999551750004662,0,119626702995,0,19530,630630,143750424825,0,184872217358,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999824537010171,0,125147136,0,0,1785,173444642540,0,1893198368,0},
{999835062418039,0,94789042845,0,1319822910,0,67886612040,0,942104166,0},
{999469416134819,0,180335501640,0,37478613900,24585,312420807596,0,348917460,0},
{999424225852169,0,77542079870,0,1104924500,0,495203976436,0,1923167025,0},
{999999999999320,0,0,0,0,680,0,0,0,0},
{999886380156215,0,52036907882,0,3353763106,0,23670821422,0,34558351375,0},
{999899712372434,0,19806132885,0,531532365,0,79066182786,0,883779530,0},
{999645378076028,0,195201154530,0,27333726420,0,70510099951,0,61576943071,0},
{999685743409025,0,1203159090,0,149199050000,0,72077776800,0,91776605085,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999940683255121,0,35419961340,0,196441471,15,19907973458,0,3792368595,0},
{999670005323379,0,63564343605,0,162376517160,0,70674169511,0,33379646345,0},
{999708408884459,0,53955025140,0,88784130450,8400,104835127340,0,44016824196,15},
{999756244499934,0,16164753885,0,45523107645,0,149251265276,0,32816373260,0},
{999999999991810,0,0,0,0,8190,0,0,0,0},
{999871653069161,0,17995344150,0,1130629500,0,108305986464,0,914970725,0},
{999834390578542,0,73321157673,0,4951,105,83842272779,0,8445985950,0},
{999811468158072,0,102506508751,0,10608953460,0,32650278532,0,42766101185,0},
{999534955792688,0,1584125406,0,857266410,2270,461145967156,0,1456846070,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999668328594775,0,91310438445,0,0,0,172719792717,0,67641174063,0},
{999523621103305,0,732410679,0,0,0,211821864986,0,263824621030,0},
{999833478470615,0,64587874560,0,15,455,99480036525,0,2453617830,0},
{999890559203793,0,4092908225,0,52932880,0,40021018006,0,65273937096,0},
{999999999998425,0,0,0,0,1575,0,0,0,0},
{999922318811103,0,1052633505,0,7828466520,0,22192699987,0,46607388885,0},
{999742381734037,0,50299023511,0,37743385680,0,148507482467,0,21068374305,0},
{999862973394044,0,819064965,0,88235799015,0,24965732996,0,23006008980,0},
{999788503430989,0,20072851860,0,32399006640,0,73738336681,0,85286373830,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999759872655279,0,1738752885,0,6430263840,0,227516704035,0,4441623961,0},
{999794965428581,0,316695305,0,46427119830,0,154018814030,0,4271942254,0},
{999733115445922,0,56464985878,0,120,8190,208948892235,0,1470667655,0},
{999903266133066,0,1099128215,0,1,0,52268837413,0,43365901305,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999581143113407,0,151687345775,0,435,0,152722046895,0,114447493488,0},
{999376081388298,0,100838137801,0,17323115643,20475,503956739893,0,1800597890,0},
{999790870585791,0,60763384500,0,0,0,143490904339,0,4875125370,0},
{999722149117029,0,2358028261,0,9975,0,275394014895,0,98829840,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999748154000897,0,17483360615,0,0,0,231082982745,0,3279655743,0},
{999805345858920,0,506971650,0,24448125,0,190964618230,0,3158103075,0},
{999747161869591,0,2514870295,0,12883005,0,172812902500,0,77497474609,0},
{999867334196886,0,57047687103,0,5168132970,0,56770214205,0,13679768836,0},
{999999999998635,0,0,0,0,1365,0,0,0,0},
{999681482838156,0,127165765203,0,108837618450,0,19946509880,0,62567268311,0},
{999874763247869,0,89171322256,0,3060,15,32760111805,0,3305314995,0},
{999541979666780,0,50378946810,0,2588166960,0,404076275730,0,976943720,0},
{999841358070819,0,124589027615,0,353500875,0,15665283320,0,18034117371,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999636517446614,0,7871542155,1,90520329915,105,265016055655,0,74625555,0},
{999761567497435,0,35845319120,0,135934683885,0,59262764806,0,7389734754,0},
{999807928592989,0,71811567885,0,2955,8295,91230539135,0,29029288740,1},
{999844130949204,0,36097360811,0,21072426390,0,98195547570,0,503716025,0},
{999999999990429,0,0,0,0,9571,0,0,0,0},
{999785961312804,0,2701069455,0,0,0,205551782790,0,5785834951,0},
{999900595355375,0,113584486,0,10935,0,98572117204,0,718932000,0},
{999719123913461,0,929735835,0,521640,0,241731737508,0,38214091556,0},
{999888380180990,0,40127710680,0,264811,19398,61320698910,0,10171125211,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999743659839469,0,12312360300,0,57882825,0,203107882651,0,40862034755,0},
{999871822818224,0,41776399386,0,4369365000,0,76201317825,0,5830099565,0},
{999795527614418,0,48628852205,0,0,0,155261103131,0,582430246,0},
{999939613182783,0,38354905,0,21693887670,0,35019411131,0,3635163511,0},
{999999999999985,0,0,0,0,15,0,0,0,0},
{999690261943684,0,170794803861,0,4354350,0,130909193584,0,8029704521,0},
{999866890892844,0,8682872885,0,14660,0,85058336510,0,39367883101,0},
{999797714539269,0,64166208450,0,7831893825,0,69332776396,0,60954582060,0},
{999517062439089,0,5729189025,0,680,0,223944202931,0,253264168275,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999850598303749,0,3583245,0,748456035,455,145533063255,0,3116593260,1},
{999651651322633,0,129862345535,0,403585,0,204169118336,0,14316809911,0},
{999660860109294,0,83302408815,0,456,45045,102968847815,0,152868588575,0},
{999805581916088,0,5335426410,0,4684680,0,99081360556,0,89996612266,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999899645499284,0,247301600,0,44833289865,0,29115898071,0,26158011180,0},
{999824277061279,0,7754663415,0,60901200360,210,99105956025,0,7961118711,0},
{999727581056310,0,61790945415,0,38326,0,139047973896,0,71579986053,0},
{999824564239979,0,212955,0,1365,3395,120418699325,0,55016842981,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999811221773639,0,21464902176,0,120,210,64092905015,0,103220418840,0},
{999945639002319,0,17024932520,0,952074060,0,29032941925,0,7351049176,0},
{999860214147279,0,3104773220,0,0,9570,56112118895,0,80568951036,0},
{999801450713394,0,4104830150,0,0,0,159372290171,0,35072166285,0},
{999999999999125,0,0,0,0,875,0,0,0,0},
{999736151456084,0,306186485,0,36141165061,0,220562533655,0,6838658715,0},
{999808594192016,0,2374447755,0,4326572250,0,183688129941,0,1016658038,0},
{999853615786235,0,93031290,0,0,0,142466744235,0,3824438240,0},
{999719665252127,0,72390003800,0,0,0,207474243153,0,470500920,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999800470131086,0,41314545853,0,65481105690,3076,66006460410,0,26727753885,0},
{999483272449588,0,93204254535,0,31663740,0,421421797397,0,2069834740,0},
{999638014022600,0,125408036145,0,54660101925,665,100717447595,0,81200391070,0},
{999820846563922,0,5045034225,0,0,0,159680470358,0,14427931495,0},
{999999999998304,0,0,0,0,1696,0,0,0,0},
{999936007566325,0,8462260620,0,100676955,0,55165893585,0,263602515,0},
{999669103557272,0,178544629200,0,87302158125,0,43532090558,0,21517564845,0},
{999772849524555,0,100785016425,0,36960,0,108119976995,0,18245445065,0},
{999728399858569,0,148823088050,0,120,121,121977721695,0,799331445,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999845313876418,0,1421880405,0,45047706075,5460,84991215706,0,23225315936,0},
{999900462133029,0,49452571455,0,475020,0,49887036705,0,197783791,0},
{999802246238486,0,88425,0,1429416,0,146126878490,0,51625365183,0},
{999710795837259,0,45025720575,0,132675648106,0,94750604385,0,16752189675,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999961856224299,0,459525,0,11403,0,23109517675,0,15033787098,0},
{999772845108431,0,14067246229,0,162949161375,105,22769136055,0,27369347805,0},
{999833937425440,0,41321954871,0,113975253,0,124026109246,0,600535190,0},
{999771435065497,0,83449725976,0,31686723915,0,100109591727,0,13318892885,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999761107095547,0,3764064634,15,21840,0,216571238904,0,18557579060,0},
{999572565478110,0,2832310995,0,848167320,0,422121585039,0,1632458536,0},
{999808013873907,0,164453364027,0,14745840,120,25444530270,0,2073485821,15},
{999692474691400,0,165106379250,0,28315489035,0,61145302147,0,52958138168,0},
{999999999999880,0,0,0,0,120,0,0,0,0},
{999530194989789,0,3152267756,0,15,0,195115668770,0,271537073670,0},
{999613447987634,0,37331084700,15,115186920240,210,233904741436,0,129265765,0},
{999929007134635,0,131682930,0,13853741265,0,46909135245,0,10098305925,0},
{999624787768900,0,55510228980,0,614872171,0,164886537529,0,154200592420,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999448542827796,0,177640519740,0,98271476775,420,273134873940,0,2410301329,0},
{999947563458323,0,697574283,0,683212755,0,16676628239,0,34379126400,0},
{999926044135733,0,13628319856,0,1,105,46438086745,0,13889457560,0},
{999785399980301,0,2927776644,0,134474567955,0,44525368545,0,32672306555,0},
{999999999981982,0,0,0,0,18018,0,0,0,0},
{999839109632213,0,117424860,0,670282670,0,160064763412,0,37896845,0},
{999775455855941,0,19433485505,0,0,15,190309718286,0,14800940253,0},
{999835834185526,0,1234919136,0,1558557015,0,160044046727,0,1328291596,0},
{999808225788448,0,2444384671,0,225,0,187428573266,0,1901253390,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999829592351509,0,15736508195,0,29900587096,1695,123670393705,0,1100157800,0},
{999924423340580,0,806563695,0,0,0,42214050055,0,32556045670,0},
{999894994608118,0,56051499525,0,210926625,1485,48179051336,0,563912911,0},
{999555837698412,0,35685547716,0,23063040,0,288521679787,0,119932011045,0},
{999999999998409,0,0,0,0,1591,0,0,0,0},
{999433901484539,0,72979630369,0,3516518460,0,488570971942,0,1031394690,0},
{999827033121484,0,1881928000,0,1607731126,8310,145913763220,0,23563447845,15},
{999922060930951,0,40919516,0,29947375815,0,21240224880,0,26710548838,0},
{999930735423071,0,35388370305,0,1276611315,1695,12533064178,0,20066529436,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999838182370205,0,5268623080,0,706500795,0,153051427385,0,2791078535,0},
{999673980499257,0,180364584120,0,36693346690,0,75505405978,0,33456163955,0},
{999829422189816,0,3474535275,0,0,0,159418699751,0,7684575158,0},
{999728064996837,0,5006028300,0,340136175,0,174403733343,0,92185105345,0},
{999999999998635,0,0,0,0,1365,0,0,0,0},
{999811707490379,0,459258555,0,0,0,172789705905,0,15043545161,0},
{999705744996405,0,1205834595,0,4702698015,9555,286662408610,0,1684052820,0},
{999711255140280,0,75655228035,0,138413773680,0,34152047360,0,40523810645,0},
{999605638290131,0,15632520255,0,62084112519,5460,313395334890,0,3249736745,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999742489153842,0,6406186185,0,28567924477,0,173389634231,0,49147101265,0},
{999804948195464,0,169236050950,0,8034845,0,16598198820,0,9209519921,0},
{999752676972087,0,6672550879,0,683212530,665,217575413146,0,22391850693,0},
{999925901534621,0,5349587460,0,1708106400,0,66363685036,0,677086483,0},
{999999999999880,0,0,0,0,120,0,0,0,0},
{999734350852296,0,26360056170,0,165754774185,0,70633350385,0,2900966964,0},
{999833781545616,0,107929371335,0,3343500615,120,21890055184,0,33055527130,0},
{999600652824061,0,124093849440,0,7074202800,0,96264653034,0,171914470665,0},
{999869185474154,0,23843119875,0,1000764765,0,86196029795,0,19774610746,665},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999815493836591,0,6017200595,0,45135090,0,134234640273,0,44209187451,0},
{999861261602404,0,115746960,0,767145,0,122226202266,0,16395681225,0},
{999576288063679,0,72248085,0,0,9555,212575049610,0,211064629071,0},
{999772432102789,0,218760550,0,4323930,0,215201936396,0,12142876335,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999935340436412,0,1216714815,0,0,0,27533744178,0,35909104595,0},
{999918302185427,0,1379560,0,890,455,59215257195,0,22481176473,0},
{999761957795759,0,19959950718,0,9549660,0,193473490997,0,24599212866,0},
{999927705825208,0,430521435,0,17797557276,8190,16516192206,0,37549895685,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999938602141886,0,4591144041,0,14190540,60060,35126486243,0,21665977230,0},
{999919058406492,0,139357195,0,52253777940,0,18949013045,0,9599445328,0},
{999548423903234,0,14881293015,0,412206795,0,257398085520,0,178884511436,0},
{999545391755466,0,6362053575,0,1159052895,0,441533148574,0,5553989490,0},
{999999999998095,0,0,0,0,1905,0,0,0,0},
{999881101766073,0,12354946215,0,891,0,86886619201,0,19656667620,0},
{999958846995172,0,17398215,15,14572950,0,21981592225,0,19139441423,0},
{999802838089372,0,222622500,0,76028727840,0,115587279798,0,5323280490,0},
{999603061053002,0,23146530,0,80430371595,4530,223204079303,0,93281345040,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999927808684366,0,476289450,0,0,9555,45217068051,0,26497948578,0},
{999927885749709,0,7323261690,0,2732850120,0,61717428778,0,340709703,0},
{999781558980594,0,3149333397,0,120,0,214337091274,0,954594615,0},
{999632591967833,0,121244880960,0,330,0,111654074066,0,134509076811,0},
{999999999999985,0,0,0,0,15,0,0,0,0},
{999940988552287,0,3172209288,0,226951740,0,55308685905,0,303600780,0},
{999848183315749,0,47684809006,0,0,105,94046136560,0,10085738580,0},
{999867298900751,0,211536083,0,64365161445,0,42229268806,0,25895132915,0},
{999930917137779,0,11987272150,0,0,210,55397508661,0,1698081200,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999793452069055,0,19561935890,0,17658515,0,186050342715,0,917993825,0},
{999853326843460,0,4200,0,15,0,98637994110,0,48035158215,0},
{999808256596347,0,442545620,0,53603550,225,186025292585,0,5221961673,0},
{999714279104009,0,83050965525,0,107633360835,0,65809207071,0,29227362560,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999913208434467,0,39127551155,0,2218737885,0,36206084928,0,9239191565,0},
{999840404058847,0,31466723195,0,101684520,0,124932784265,0,3094749173,0},
{999822676394392,0,56184757475,0,9828,0,90230754335,0,30908083970,0},
{999736399903058,0,122520058445,0,71583046095,0,13827405447,0,55669586955,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999782267272463,0,88896381,0,15,0,201139118180,0,16504712961,0},
{999610874876853,0,30496740125,0,7210985175,0,351181594076,0,235803771,0},
{999880575428628,0,57426070362,0,17746,105,30892101411,0,31106381748,0},
{999890794221530,0,328862370,0,0,0,99645983100,0,9230933000,0},
{999999999999985,0,0,0,0,15,0,0,0,0},
{999706213749437,0,27919681170,0,13009170438,0,237137667925,0,15719731030,0},
{999834399605219,0,228165,0,8235045,0,123812459871,0,41779471700,0},
{999804083407832,0,25592489600,0,116537270850,0,42727525277,0,11059306441,0},
{999783904545530,0,72435021339,0,20070014965,0,116088271791,0,7502146375,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999857468770454,0,30639243945,0,13290412815,0,98408242886,0,193329900,0},
{999875931215710,0,5903773365,0,397567170,0,108457863040,0,9309580715,0},
{999809257696206,0,15296059173,0,1575134330,0,167290096066,0,6581014210,15},
{999772546849104,0,587288661,0,15,0,224043365575,0,2822496645,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999741004411534,0,92409766400,0,80094463215,0,72139489276,0,14351869575,0},
{999690683284640,0,1021986765,0,120045,210,254892215810,0,53402392530,0},
{999781431895475,0,49387427940,0,892536375,0,163224281700,0,5063858510,0},
{999958910116336,0,522776003,0,943002060,120,16558687771,0,23065417710,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999914448568464,0,58599994680,0,2154602115,16380,12961450981,0,11835367380,0},
{999844791006360,0,2128571460,0,3045,0,134644539033,0,18435880102,0},
{999925889227447,0,16647113598,0,6430263855,0,46425469605,0,4607925495,0},
{999809775690436,0,11810835,0,3643005,0,131958554089,0,58250301635,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999956088482815,0,7836200,0,8092126770,0,35148856190,0,662698025,0},
{999948805497856,0,465683610,0,225,4095,44465613694,0,6263200520,0},
{999939503181495,0,570410,0,9990,0,39750100595,0,20746137510,0},
{999664118490676,0,177751208370,0,7282290,420,153384751366,0,4738266878,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999873476095326,0,243356040,0,937345500,0,103848548835,0,21494654299,0},
{999822679978624,0,66392345985,0,15651034351,0,64720151920,0,30556489120,0},
{999938030342446,0,25957870830,0,504203700,0,27172163375,0,8335418984,665},
{999612367512924,0,31245283645,0,82364393475,0,267734635506,0,6288174450,0},
{999999999989080,0,0,0,0,10920,0,0,0,0},
{999633084632695,0,3751631151,0,512311800,0,361209131145,0,1442293209,0},
{999868129689735,0,3610962755,0,76915020,0,70187284520,0,57995146395,1575},
{999698878739304,0,86174069475,0,330330,0,201945815316,0,13001045575,0},
{999897585891409,0,54008811675,0,13114920,0,35220653700,0,13171528296,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999845243253042,0,4967890020,0,0,210,94915174228,0,54873682500,0},
{999763295728097,0,162428000490,0,31822851060,0,41216618150,0,1236802203,0},
{999756286780562,0,73860360,0,5085039960,0,201533981008,0,37020338110,0},
{999930246047266,0,134971200,0,29546667696,0,24906269553,0,15166044285,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999683675303919,0,2423540,0,2282280,0,148146431796,0,168173558465,0},
{999745977171755,0,70278477570,0,0,0,130726924755,0,53017425920,0},
{999418413461765,0,189461493470,0,129198147015,0,258813916490,0,4112981260,0},
{999900411444525,0,4039035,0,23195055,0,97352023675,0,2209297710,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999801383884911,0,931214130,0,72538476465,1,117397539623,0,7748884870,0},
{999704159491632,0,7185777965,0,159916537365,0,93651730830,0,35086462208,0},
{999968710135426,0,8675075670,0,140324940,241,19954660983,0,2519802740,0},
{999788324354295,0,83597177575,0,0,0,76856224495,0,51222243635,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999806507220530,0,5576566415,0,0,0,167086189480,0,20830023575,0},
{999910766546242,0,4096079187,0,2300705,1,81493836015,0,3641237850,0},
{999581433405395,0,106728273060,0,1785,0,129785808475,0,182052511285,0},
{999827894089921,0,97332960,0,17535696360,15,150028254318,0,4444626426,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999671249132364,0,10262841606,0,65874528720,1365,135673562600,0,116939933345,0},
{999850409604890,0,33329730,0,0,0,148014184370,0,1542881010,0},
{999893314998110,0,205731435,0,225,0,104094774575,0,2384495655,0},
{999841361109955,0,105286728540,0,831426275,0,52100228035,0,420507195,0},
{999999999998620,0,0,0,0,1380,0,0,0,0},
{999554400470249,0,163855428030,0,35598162600,0,245988187728,0,157751393,0},
{999683290728005,0,509052210,0,0,0,249058551260,0,67141668525,0},
{999501685924435,0,67340281765,0,271476780,0,429661973925,0,1040343095,0},
{999873160091006,0,13863438345,0,18219175,0,57653342591,0,55304908883,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999840437008166,0,3691466058,0,0,226,146798258410,0,9073267140,0},
{999891134816879,0,68174987875,0,2292907855,0,15707769690,0,22689517701,0},
{999685566261934,0,21026458245,0,210,8190,289957198021,0,3450073400,0},
{999939231030560,0,12588114365,0,160137705,0,47240324175,0,780393195,0},
{999999999999894,0,0,0,0,106,0,0,0,0},
{999680230009071,0,211982407410,0,13945932000,0,40337844949,0,53503806570,0},
{999723314750136,0,120090884025,0,210,0,141209992079,0,15384373550,0},
{999715632026176,0,810281346,0,158611282830,0,54622970403,0,70323439245,0},
{999620855027335,0,18075706194,0,8378125281,1,351991931894,0,699209295,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999792119735039,0,78960397638,0,564684120,0,128277921690,0,77261513,0},
{999949427707805,0,27544521715,0,77837775,0,21580624765,0,1369307940,0},
{999932495224239,0,33215419658,0,125580,0,34151417168,0,137813355,0},
{999736511480575,0,34258480380,0,145569824400,0,64907630710,0,18752583935,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999761863978579,0,33123009705,0,115328863650,0,66262477776,0,23421670290,0},
{999741228121725,0,26052414515,0,0,0,225067526255,0,7651937505,0},
{999846584944807,0,11860236018,0,34799531130,0,88133299875,0,18621988170,0},
{999970495794498,0,218675,0,0,0,12601407207,0,16902579620,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999753954614095,0,84624160635,0,1179285345,210,111270010560,0,48971929155,0},
{999902237667387,0,17751045978,0,322972650,0,79109495215,0,578818770,0},
{999786794434363,0,1266318900,0,225,1,206065551450,0,5873695061,0},
{999846165497444,0,63902604515,0,450,0,81144108426,0,8787789165,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999822599266377,0,122169521805,0,8766027270,0,18829420273,0,27635764275,0},
{999806861537877,0,3312336380,0,11220540,13651,183433786558,0,6381104994,0},
{999568585448940,0,925887865,0,435014580,0,429351078480,0,702570135,0},
{999852667361495,0,4968501720,0,97192080,0,114255613080,0,28011331625,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999764495536027,0,122720245095,0,17016613020,0,40428432195,0,55339173663,0},
{999699730262935,0,64726438885,0,0,0,159142258080,0,76401040100,0},
{999834985185675,0,84946051725,0,502341840,0,72951144385,0,6615276375,0},
{999545397387100,0,602002765,0,0,0,199553323295,0,254447286840,0},
{999999999998425,0,0,0,0,1575,0,0,0,0},
{999851857397655,0,65797180035,0,0,0,81381789758,0,963632552,0},
{999942725156229,0,28761930,0,6288645090,2730,47747855683,0,3209578338,0},
{999917792743564,0,2503835895,0,26966940,0,30239222496,0,49437231105,0},
{999892673806625,0,31914023505,0,37703505840,0,36669797110,0,1038866920,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999946847372270,0,32155614940,0,0,121,20085425969,0,911586700,0},
{999929938453767,0,884914695,0,3084378795,0,23427510048,0,42664742695,0},
{999944551304782,0,130818870,0,120,120,19374732590,0,35943143518,0},
{999809127168024,0,36906877498,0,32248796580,0,101872877913,0,19844279985,0},
{999999999999879,0,0,0,0,121,0,0,0,0},
{999865023129264,0,729494235,0,95266800720,0,21268982733,0,17711593048,0},
{999798820852615,0,4442963645,0,64600106445,785,96216082860,0,35919993650,0},
{999840734220219,0,25270167518,0,25913607720,0,44149819113,0,63932185430,0},
{999866269332028,0,36202785,0,314837005,1,133347365666,0,32262515,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999698951934070,0,144969556425,0,0,0,146287911420,0,9790598085,0},
{999828301549402,0,604297275,0,2563781220,0,166901324115,0,1629047988,0},
{999799851522845,0,148445365355,0,1785,0,46313273595,0,5389836420,0},
{999824180556542,0,120170610,0,29679838188,0,144464326945,0,1555107715,0},
{999999999999320,0,0,0,0,680,0,0,0,0},
{999763906112697,0,65091873798,0,15,0,170315894875,0,686118615,0},
{999861105024504,0,8137007718,0,0,0,130500501910,0,257465868,0},
{999941672610730,0,475074225,0,0,0,31559773845,0,26292541200,0},
{999791849366977,0,26844899655,0,403132710,8190,155868806893,0,25033785575,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999621644743674,0,44022189393,0,14774760,785,229341768083,0,104976523305,0},
{999634981417440,0,137480098995,0,15,0,132500050225,0,95038433325,0},
{999773018620813,0,47038618575,0,2865604770,121,170559170121,0,6517985600,0},
{999450067067625,0,75643476865,0,8619030420,0,464893724865,0,776700225,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999838653339944,0,40686520695,0,0,0,118719970721,0,1940168640,0},
{999943749144013,0,31309425,0,21404135745,121,17702632521,0,17112778175,0},
{999765393425147,0,3542647983,0,1785,0,231042133010,0,21792075,0},
{999699834200935,0,78308555535,0,91050828975,120,115062625686,0,15743788749,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999762036692785,0,15830396715,0,13952301090,0,207064561160,0,1116048250,0},
{999794697358547,0,11280341520,0,0,0,192685766460,0,1336533473,0},
{999704701992788,0,150641729973,0,41953201290,0,86893562864,0,15809513085,0},
{999821196291692,0,175987905,0,98484360,0,173632301055,0,4896934988,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999721306366947,0,1594443515,0,15,0,178375967010,0,98723222513,0},
{999768214910317,0,63067301430,0,0,105,148082498388,0,20635289760,0},
{999858675997070,0,73905986715,0,3045050190,0,57046247700,0,7326718325,0},
{999796862221152,0,63767385,0,0,210,195874755280,0,7199255973,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999442084894282,0,139435760380,0,691892580,300300,215998601798,0,201788550660,0},
{999756285441130,0,83221968216,0,102832441530,0,14678275369,0,42981873755,0},
{999910294325730,0,59412944970,0,1384503135,120,28326260265,0,581965780,0},
{999878425036876,0,101301424618,0,680,0,17252168795,0,3021369031,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999603038886768,0,54308007998,0,862140825,0,341250667390,0,540297019,0},
{999838881578130,0,18704458073,0,0,0,86467697061,0,55946266736,0},
{999853067005439,0,127931629376,0,79493505,0,9593882545,0,9327989135,0},
{999977902256595,0,1418392010,0,951599040,120,19014690620,0,713061615,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999952341271871,0,1047643231,0,1931079150,210,44270905483,0,409100055,0},
{999704988148354,0,2996980890,0,79750671000,0,212238279705,0,25920051,0},
{999910750416299,0,5828012425,0,611148735,15,82461747405,0,348675121,0},
{999772086123299,0,20094743035,0,163774550940,0,41332978016,0,2711604710,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999867518860024,0,50523170880,0,211,0,64232873930,0,17725094955,0},
{999663929337729,0,82704504575,0,7565543520,0,62460797666,0,183339816510,0},
{999896466462700,0,26821939630,0,12729491775,0,63485263415,0,496842480,0},
{999882000403273,0,23595220705,0,14303590665,0,67233904757,0,12866880600,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999954436819179,0,2926333050,0,0,2850,22709641570,0,19927203351,0},
{999804539175514,0,2953105410,0,0,0,188878733525,0,3628985551,0},
{999867494876860,0,45744860,0,1150710,0,101379265795,0,31078961775,0},
{999909794678749,0,72206435,0,1366,0,89943721590,0,189391860,0},
{999999999999565,0,0,0,0,435,0,0,0,0},
{999742753267330,0,274231545,0,1430900,0,236277318055,0,20693752170,0},
{999755611526292,0,28634893486,0,76328737485,2955,110329182600,0,29095657167,15},
{999915702330139,0,30931970475,0,720825,0,39966135951,0,13398842610,0},
{999962951565279,0,497922196,0,0,3075,21034439670,0,15516069675,105},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999888724253329,0,2771314455,0,1014136515,0,3424740180,0,104065555521,0},
{999760703342055,0,18456614610,0,15091440,0,179162476825,0,41662475070,0},
{999905720453399,0,29059675415,0,17492236546,0,45022383150,0,2705251490,0},
{999893040265080,0,43622716020,0,1508827320,0,57916063955,0,3912127625,0},
{999999999999985,0,0,0,0,15,0,0,0,0},
{999844663403844,0,25836369240,0,0,0,129220571446,0,279655470,0},
{999835604557543,0,78440086860,0,470,0,83784191267,0,2171163860,0},
{999953203826724,0,15395835,0,25213519695,0,18701423345,0,2865834401,0},
{999499153844209,0,114317016626,0,63190747620,0,271478496915,0,51859894630,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999519469892465,0,2534040970,0,795314520,680,474452479545,0,2748271820,0},
{999750776918205,0,139977889445,0,32162130,0,104536814630,0,4676215590,0},
{999862922113617,0,22730,0,6233942925,0,126727087613,0,4116833115,0},
{999879780843155,0,5994574440,0,1905,0,83689176755,0,30535403745,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999859704171463,0,39358493125,0,4905851615,0,44135580792,0,51895903005,0},
{999795183454633,0,228273420,0,108649150675,120,87016644732,0,8922476420,0},
{999537739019600,0,5174831025,0,120,0,228323854090,0,228762295165,0},
{999929339322284,0,3044870340,0,62614364685,120,4277923431,0,723519140,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999859392942149,0,88986613325,0,56035980,0,44648827005,0,6915581541,0},
{999863545742378,0,114660,0,748456021,0,134279049643,0,1426637298,0},
{999928154640712,0,5205150615,0,379321800,0,66260518860,0,368013,0},
{999705263101885,0,135564806061,0,75075,0,152025328849,0,7146688130,0},
{999999999999335,0,0,0,0,665,0,0,0,0},
{999681261016594,0,89757762390,0,0,0,87566016725,0,141415204291,0},
{999943954724870,0,5965925420,0,33286678425,15,14381283360,0,2411387910,0},
{999847227630151,0,2694625275,0,2657655,0,71791595724,0,78283491195,0},
{999934327090164,0,1743543795,0,970494540,0,62584682685,0,374188816,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999933411663405,0,10268004453,0,180180,0,52678954811,0,3641197151,0},
{999911197065466,0,85954050,0,49503113205,0,21633806529,0,17580060750,0},
{999674869351596,0,915493691,3003,837992625,1365,317977666875,0,5399490845,0},
{999842697669997,0,9993953585,0,47865416235,0,93105414958,0,6337545225,0},
{999999999999985,0,0,0,0,15,0,0,0,0},
{999804635575721,0,34372500411,0,11508,0,107876746340,0,53115166020,0},
{999942029620575,0,3746663115,0,31036111,0,39972708559,0,14219971640,0},
{999844122851767,0,19320,0,105,0,110829056550,0,45048072258,0},
{999916359298141,0,969341835,0,6841674840,0,71090705779,0,4738979405,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999780449072553,0,55285198365,0,70922676825,1365,72498660267,0,20844390625,0},
{999856494807697,0,10826152155,0,15,0,64817023463,0,67862016670,0},
{999955446409584,0,2669690805,0,1575,0,10608394301,0,31275503735,0},
{999949697200427,0,22082703105,0,644053620,0,22887065827,0,4688977021,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999909453955418,0,1466395206,0,0,0,37648680236,0,51430969140,0},
{999850832012275,0,60667747210,0,40950,0,72421534305,0,16078665260,0},
{999849193529857,0,1954684215,0,0,0,115377131298,0,33474654630,0},
{999839312798454,0,58992570,0,0,0,27919692600,0,132708516376,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999724535350571,0,23389158,0,59692263540,2835,215735455595,0,13538301,0},
{999768479776351,0,198789801,0,44960525610,0,182312600580,0,4048307658,0},
{999663153025023,0,20022131836,0,16367567580,9555,300271140311,0,186125695,0},
{999836968116864,0,1647713096,0,9512242740,0,151460393435,0,411533865,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999881000623308,0,49156293,0,0,0,114439770435,0,4510449964,0},
{999769500996041,0,30034499498,0,1531635,5460,140334209631,0,60128757735,0},
{999750467493079,0,83755580133,0,0,0,165615478077,0,161448711,0},
{999772818590299,0,14221641750,0,22819106310,0,163314645770,0,26826015871,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999800419386909,0,55125,0,196396200,0,198807716176,0,576445590,0},
{999839659761854,0,22397327796,0,86644973415,0,37111782225,0,14186154710,0},
{999788958396832,0,25164610590,0,91455330,15,161702469900,0,24083067333,0},
{999558012740960,0,89894933730,0,15,0,351046338680,0,1045986615,0},
{999999999991810,0,0,0,0,8190,0,0,0,0},
{999732988814835,0,96948466680,0,38110493850,0,77708529485,0,54243695150,0},
{999649354439359,0,8025471090,0,92591787,0,209246734916,0,133280762848,0},
{999874094836210,0,3396286215,0,0,0,114684188205,0,7824689370,0},
{999943544528957,0,5143713213,0,1935404835,8190,49356523170,0,19821635,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999776938152551,0,72483120,0,0,2940,220901621143,1,2087740245,0},
{999964155069911,0,4248077595,0,17343691,0,31387346335,0,192162468,0},
{999757637188811,0,5304837331,0,172758915,0,30834916045,0,206050298898,0},
{999763119133058,0,118628984985,0,72322645395,0,33322430452,0,12606806110,0},
{999999999997164,0,0,0,0,2836,0,0,0,0},
{999839533762032,0,62929538975,0,11403,0,78475165309,0,19061522281,0},
{999779273968031,0,45069326865,0,137291700,105,171862877233,0,3656536066,0},
{999792450030374,0,120202084485,0,15,0,86638254386,0,709630740,0},
{999815270353051,0,21469184100,0,0,0,139699849070,0,23560613779,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999827385824579,0,147770529975,0,99908446,0,10205016425,0,14538720575,0},
{999893394877524,0,574545420,0,34163584695,0,60710195056,0,11156797305,0},
{999900714592779,0,1217222370,0,0,2730,81598237590,0,16469944531,0},
{999913226062627,0,44386656405,0,114660,0,42228716763,0,158449545,0},
{999999999999335,0,0,0,0,665,0,0,0,0},
{999839114443173,0,15765,0,655748,0,123890635434,0,36994249880,0},
{999932003932949,0,40695170336,0,8420641776,0,11344904991,0,7535349948,0},
{999733538916456,0,26394504466,0,156794858220,0,75844157770,0,7427563088,0},
{999966568631253,0,1840486,0,2106653640,0,31239815463,0,83059158,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999925365103042,0,6951914376,0,0,225,19048452224,0,48634530133,0},
{999964018519206,0,131715,0,3045,0,17399265150,0,18582080884,0},
{999825514058368,0,1389823830,0,31975331115,15,134049969341,0,7070817331,0},
{999817496907189,0,20635842390,0,135183513465,0,11297813866,0,15385923090,0},
{999999999994435,0,0,0,0,5565,0,0,0,0},
{999873907305891,0,38787156409,0,12345375,0,87005646465,0,287545860,0},
{999837609347019,0,13373548420,0,31300880535,0,50619693206,0,67096530820,0},
{999837091128547,0,60833243933,0,26769577800,0,63392715277,0,11913334443,0},
{999813919362979,0,33243736500,0,686455771,682110,138250035425,0,13899727215,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999669903431784,0,18894924405,0,94191217575,210,207035853226,0,9974572800,0},
{999775816422232,0,1280683005,0,2940,0,214312262838,0,8590628985,0},
{999962722498356,0,1303185,0,1776232200,0,34247233369,0,1252732890,0},
{999610269756109,0,1540109056,0,373753380,0,387047783790,0,768597665,0},
{999999999999790,0,0,0,0,210,0,0,0,0},
{999823173601058,0,155849532790,0,9014580,0,20188446379,0,779405193,0},
{999730795315579,0,47860306515,0,161070,15,210946658466,0,10397558355,0},
{999699527961473,0,168015109893,0,29651054370,0,44175808229,0,58630066035,0},
{999773628555730,0,11612720100,0,20962305,0,197243992360,0,17493769505,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999863414042476,0,18365089743,0,0,1,116735968390,0,1484899390,0},
{999571049975175,0,2654531880,0,0,0,175575142270,0,250720350675,0},
{999776008573530,0,130633634250,0,56128772700,0,35134828330,0,2094191190,0},
{999617189961955,0,37923167100,0,123274112535,0,221557967397,0,54791013,0},
{999999999999999,0,0,0,0,1,0,0,0,0},
{999950297843127,0,56213535,0,16428218625,0,26307907483,0,6909817230,0},
{999928255794832,0,61116998040,0,61786650,210,9451547463,0,1113872805,0},
{999636979607300,0,57497668950,0,522080940,0,152201125610,0,152799517200,0},
{999703182135879,0,4702845,0,105,1,154373275524,0,142439885646,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999839133329886,0,92401426683,0,0,1365,66306986805,0,2158255261,0},
{999502763753329,0,170412842955,0,91516961070,0,232097163971,0,3209278675,0},
{999805645173951,0,11166261016,0,0,0,116269349430,0,66919215603,0},
{999972975885884,0,446141585,0,644413785,0,8824501081,0,17109057665,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999930284566013,0,15305235095,0,0,0,30093672567,0,24316526325,0},
{999891052489664,0,44223387000,0,3798584791,105,45696567795,0,15228970645,0},
{999791278636875,0,2582281585,0,133715102430,0,48268494645,0,24155484465,0},
{999854363135409,0,5242999050,0,24114720630,210,114046305811,0,2232838890,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999803816654941,0,106202103840,0,1365,0,41823902363,0,48157337491,0},
{999885052406199,0,62786025,0,487638936,0,114385487485,0,11681355,0},
{999872878477334,0,9747967740,0,0,0,112219459801,0,5154095125,0},
{999821106446120,0,10135585425,0,0,0,157414409365,0,11343559090,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999891876334319,0,730270390,0,458558101,0,106540585470,0,394251720,0},
{999611610596125,0,70995860565,0,2045,165165,131748015204,0,185645360896,0},
{999834966388810,0,1776187140,0,15,0,162481792640,0,775631395,0},
{999813492178134,0,161651858100,0,680,0,8540603171,0,16315359915,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999748402328819,0,25090026330,0,15,210,195483064211,0,31024580415,0},
{999859142530887,0,8651763121,0,18015917010,0,113596157502,0,593631480,0},
{999851971133893,0,55433865,0,0,120,147319889301,0,653542821,0},
{999954779020038,0,309451415,0,0,0,28098258962,0,16813269585,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999902343521216,0,62395370499,0,136906770,0,34865737400,0,258464115,0},
{999823618951727,0,112644575905,0,124488,0,46796470385,0,16939877495,0},
{999634185658494,0,24185707455,0,7567560,0,244792586561,0,96828479930,0},
{999583121545745,0,171771618000,0,15473626350,1365,229589968650,0,43239890,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999918934932382,0,156290,0,3060,1575,80819387130,0,245519563,0},
{999515451604718,0,55900729982,0,1179283560,0,426961224533,0,507157207,0},
{999759999448811,0,164716947213,0,330331,0,73433110805,0,1850162840,0},
{999858174116995,0,583444800,0,999893895,0,129073215590,0,11169328720,0},
{999999999999879,0,0,0,0,121,0,0,0,0},
{999948239141457,0,13335688,0,21528356230,0,12403946970,0,17815219655,0},
{999889866193345,0,3873828273,0,42525,1380,91561753587,0,14698180890,0},
{999933898446178,0,44440592208,0,895182060,0,7221510424,0,13544269130,0},
{999957509797400,0,100690920,0,4153809660,1680,14775128220,0,23460572120,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999933821198725,0,21333886340,0,172202940,0,42603412525,0,2069299470,0},
{999867182752522,0,6284363730,0,401531130,0,124394068880,0,1737283738,0},
{999896148475578,0,14727525,0,3706316315,0,97028723655,0,3101756927,0},
{999714888169385,0,193016944050,0,20127547440,0,43013443825,0,28953895300,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999867652210235,0,3342775815,0,0,0,125957990555,0,3047023395,0},
{999777334653269,0,568533840,0,147623035560,0,27216709715,0,47257067616,0},
{999716423775560,0,4323338565,0,369134220,0,171864423870,0,107019327785,0},
{999650332024305,0,21884118720,0,438964320,0,317189961695,0,10154930960,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999964368276204,0,1027640685,0,15,0,31458564375,0,3145518721,0},
{999836570710132,0,269919783,0,0,0,144527067780,0,18632302305,0},
{999948085178835,0,32431983450,0,125411730,0,17543589960,0,1813836025,0},
{999747892396414,0,902256110,0,1809457650,0,248591675491,0,804214335,0},
{999999999999670,0,0,0,0,330,0,0,0,0},
{999776154443869,0,42644725341,0,125121511515,0,31650159942,0,24429159333,0},
{999901631614572,0,52751874175,0,15,6306435,43164453685,0,2445751118,0},
{999676632640056,0,12535511625,0,66058402410,0,243187053105,0,1586392804,0},
{999800814136613,0,25717993051,0,89678604016,1590,53599243050,0,30190021680,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999869695524904,0,5719841855,0,16516980480,0,39008349376,0,69059303385,0},
{999840004833375,0,4802076105,0,22536204600,0,102989181880,0,29667704040,0},
{999776887439993,0,81951892740,0,0,0,64427568011,0,76733099256,0},
{999827984495279,0,158723787213,0,0,0,9345788628,0,3945928880,0},
{999999999998425,0,0,0,0,1575,0,0,0,0},
{999816005815402,0,4227203610,0,582982400,0,166301422733,0,12882575855,0},
{999983994996454,0,4982306446,0,0,0,8921293805,0,2101403295,0},
{999945601444296,0,5272179293,0,593422830,0,48064096301,0,468857280,0},
{999893131124891,0,36810542630,0,0,0,9984139714,0,60074192765,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999895504342334,0,41414378175,0,345,0,59748119800,0,3333159346,0},
{999746982994439,0,13255187030,0,180570570180,0,57495007176,0,1696241175,0},
{999737871876458,0,123462587445,0,41556039736,0,87449470655,0,9660025706,0},
{999846121710945,0,116831530845,0,2842925085,0,11356755560,0,22847077565,0},
{999999999999880,0,0,0,0,120,0,0,0,0},
{999626159871294,0,101603447400,0,3515380260,0,94554126046,0,174167175000,0},
{999603914400874,0,195513360,0,151561410,330,395499944811,0,238579215,0},
{999891896419163,0,17701730865,0,1303908606,0,78609642685,0,10488298681,0},
{999910824191054,0,2920332481,0,105,120,31029418780,0,55226057460,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999882816592946,0,442056828,0,59824159395,5460,32844996776,0,24072188595,0},
{999871261536261,0,3219093633,0,50720670,0,101610259680,0,23858389756,0},
{999799047281164,0,48065925066,0,0,0,113797703210,0,39089090560,0},
{999899506705929,0,55545455,0,46410,0,92781672461,0,7656029745,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999588644711376,0,24164868,0,0,0,204097458165,0,207233665591,0},
{999868368377874,0,680,0,0,0,92142003551,0,39489617895,0},
{999803277350820,0,48949895,0,11505585,0,191073841265,0,5588352435,0},
{999865099543616,0,51091580750,0,0,0,82627372549,0,1181503085,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999724996719264,0,62693030766,0,379321800,15,180935747428,0,30995180727,0},
{999951005033651,0,630772221,0,0,0,20743967753,0,27620226375,0},
{999892408909550,0,9524890830,0,176486730,15,96649888715,0,1239824160,0},
{999940840278917,0,209055,0,120,0,43287931583,0,15871580325,0},
{999999999999790,0,0,0,0,210,0,0,0,0},
{999784019000295,0,26570446910,0,1397775,0,168112680220,0,21296474800,0},
{999877017160247,0,976584170,0,90300,0,121880781978,0,125383305,0},
{999944064901140,0,248509460,0,8134521060,0,14953205780,0,32598862560,0},
{999713396107744,0,202198875845,0,989863875,0,83401311436,0,13841100,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999802952613657,0,34605353520,0,54872197380,0,98482142863,0,9087692580,0},
{999951829555590,0,3352202805,0,2078505,0,27491966455,0,17324196645,0},
{999873432731169,0,4636545760,0,0,0,118064776761,0,3865946310,0},
{999923769801844,0,106226720,0,56731193610,0,11874472455,0,7518305371,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999654647945894,0,8329153875,0,283558275,0,189344605461,0,147394736495,0},
{999878609552345,0,29948515175,0,10908654120,0,34568664390,0,45964613970,0},
{999584891418206,0,3951997405,0,503993490,0,407652905706,0,2999685193,0},
{999866850796561,0,10586385,0,105387882810,0,27584205993,0,166528251,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999918909453855,0,2078505,0,660870,0,21482147145,0,59605659625,0},
{999886170638616,0,13070391421,0,15,0,88354390765,0,12404579183,0},
{999840333868546,0,853892750,0,3322158840,0,153692829976,0,1797249888,0},
{999975334373963,0,3667800,0,1161825,0,15218309339,0,9442487073,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999841350274666,0,62412470,0,51840514635,0,104799024525,0,1947773704,0},
{999780760077041,0,88751854780,0,17624900685,210,56130474224,0,56732693060,0},
{999624786370974,0,4064025,0,99226822905,0,213586012636,0,62396729460,0},
{999754601845465,0,90506860080,0,0,1575,154401822350,0,489470530,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999899116549866,0,753576090,0,210,0,84003079653,0,16126794181,0},
{999955972896366,0,216592740,0,0,0,27018600099,0,16791910795,0},
{999762661077714,0,2510654055,0,210,0,199997358220,0,34830909801,0},
{999950934586950,0,4182734300,0,2655252600,0,41990152673,0,237273477,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999800020868190,0,2268722705,0,15,0,197300361410,0,410047680,0},
{999712480037850,0,288596805,0,3060,0,127998454890,0,159232907395,0},
{999671784313915,0,117787536330,0,30,0,96145580320,0,114282569405,0},
{999626426395995,0,81971941545,0,53916594335,420,237360006470,0,325061235,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999477345780938,0,76701762806,0,17036141956,2730,427990181250,0,926130320,0},
{999959576724661,0,3023745530,0,32852820,0,37205065069,0,161611920,0},
{999802942521000,0,107880140139,0,38610000,0,64909789560,0,24228939301,0},
{999893875027351,0,33085739505,0,0,0,68420802814,0,4618430330,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999876085874341,0,88710315,0,65690637870,0,40793581328,0,17341196146,0},
{999788983032217,0,952638120,0,680,0,210024186478,0,40142505,0},
{999955328019838,0,8048774370,0,0,0,35727598272,0,895607520,0},
{999882756957967,0,6642153080,0,0,150150,75133800147,0,35466938656,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999940702747229,0,3762034824,0,0,90300,55407635357,0,127492290,0},
{999866216241136,0,11201434885,0,64324275,0,122161859681,0,356140023,0},
{999806769627825,0,9805097115,0,0,0,181508800295,0,1916474765,0},
{999867918333114,0,105,0,0,0,96763358971,0,35318307810,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999832851217524,0,142916910,0,187297110,0,157878358315,0,8940210141,0},
{999863016628310,0,40849757160,0,0,455,80654242215,0,15479371860,0},
{999752251310054,0,58767959970,0,88798725015,0,79168387501,0,21013617460,0},
{999733214726325,0,1887991980,0,7387380,0,171494917650,0,93394976665,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999826059519194,0,246472800,0,210,8190,173693906930,0,92675,1},
{999907952480799,0,50245231855,0,1358611800,0,35218041935,0,5225633611,0},
{999910486448455,0,8616474603,0,244679191,1575,80314900871,0,337495305,0},
{999870846397748,0,26257534656,0,60442200,0,101387635080,0,1447990316,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999879661108331,0,31490396210,0,0,0,66703695774,0,22144799685,0},
{999925437621978,0,33032448555,0,1634712170,1575,39895194370,0,21352,0},
{999802383252297,0,84422001300,0,65900586571,0,7397097024,0,39897062808,0},
{999845604856499,0,88844571615,0,127698480,0,17582359095,0,47840514311,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999899976553309,0,75469165905,0,0,0,18255200435,0,6299080351,0},
{999819725333969,0,31232880,0,0,0,166845617570,0,13397815581,0},
{999508177775170,0,10950024540,0,33229770,0,455835387935,0,25003582585,0},
{999678562669784,0,28912780865,0,2927882686,0,289458804465,0,137862200,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999915913737932,0,43048588695,0,1365,0,20948113750,0,20089558258,0},
{999906552635519,0,81044883591,0,413775180,0,4251884975,0,7736820735,0},
{999916984354220,0,206565900,0,0,0,72569521265,0,10239558615,0},
{999895801469784,0,300660481,0,37478581140,0,57427914990,0,8991373605,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999899290947051,0,58006253165,0,1786,0,18989148327,0,23713649671,0},
{999758881452155,0,21766402905,0,10166987730,0,198439711820,0,10745445390,0},
{999728317606699,0,3956486725,0,48932924040,0,218774894010,0,18088526,0},
{999827796114290,0,47985,0,3599115,0,122181314375,0,50018924235,0},
{999999999999999,0,0,0,0,1,0,0,0,0},
{999814665254434,0,13751785101,0,141683086545,0,25290859755,0,4609014165,0},
{999692835365766,0,179186579355,0,1,5460,118619054064,0,9358995354,0},
{999837150632979,0,71172575566,0,11744868135,0,75345972135,0,4585951185,0},
{999871355868819,0,35017902480,0,210,1575,83384814360,0,10241412556,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999947103208505,0,16390426965,0,2792549760,0,26157811219,0,7556003551,0},
{999909868032505,0,22769305630,0,8411157756,0,58774759589,0,176744520,0},
{999751606671526,0,106058544075,0,23929564935,0,117064466865,0,1340752599,0},
{999921488865481,0,3383751820,0,300570270,0,70538744799,0,4288067630,0},
{999999999998425,0,0,0,0,1575,0,0,0,0},
{999812377219979,0,20341150651,0,613407795,0,163310745115,0,3357476460,0},
{999809949119546,0,3330210,0,244680765,0,189418772825,0,384096654,0},
{999789900934043,0,590851425,0,0,0,208108909187,0,1399305345,0},
{999968941833980,0,10001265615,0,4911031125,0,16015586935,0,130282345,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999908834780475,0,5717075,0,0,0,90813789320,0,345713130,0},
{999812380409112,0,51765744450,0,68712949995,0,59947770670,0,7193125773,0},
{999791199523402,0,45651616740,0,646277835,1,147069317525,0,15433264497,0},
{999715865374476,0,310697625,0,275760,0,253335502521,0,30488149618,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999829412187465,0,28609761470,0,1319055675,0,135233062805,0,5425932585,0},
{999936773369614,0,16093387290,0,2583945,4201,29313003380,0,17817651570,0},
{999976078149565,0,131492340,0,645705060,0,8151464295,0,14993188740,0},
{999838141885872,0,4796279113,0,5903188215,0,81695385540,0,69463261260,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999836761210496,0,473142090,0,2479216740,0,160205479334,0,80951340,0},
{999936495429510,0,50252925480,0,814043700,0,6267525285,0,6170076025,0},
{999760460148807,0,18872755546,0,15918630,0,153653176500,0,66998000517,0},
{999889484839499,0,1159526551,0,680,0,98481414965,0,10874218305,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999942716808689,0,17358913515,0,2563781220,0,34011469955,0,3349026621,0},
{999877507803896,0,95595318,0,52240788600,0,50511700941,0,19644111245,0},
{999847528702540,0,6575251,0,1440105,0,112605831778,0,39857450326,0},
{999822256708149,0,29902040075,0,0,0,147746776380,0,94475396,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999901551291899,0,104556900,0,35505,0,90948479275,0,7395636421,0},
{999970857454906,0,3025171,0,9390381000,0,19232205623,0,516933300,0},
{999875956308399,0,52615733865,0,14583605611,0,31675835175,0,25168516950,0},
{999968392525696,0,99660890,0,15,0,28476431549,0,3031381850,0},
{999999999999999,0,0,0,0,1,0,0,0,0},
{999931789936845,0,170850,0,1785,0,34124637892,0,34085252628,0},
{999813919424038,0,66908205,0,2045949360,0,183686150887,0,281567510,0},
{999715897267242,0,152641940340,0,43723680,0,128743100940,0,2673967798,0},
{999729635056047,0,2201063250,0,164847560790,0,94420494148,0,8895825765,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999862799942886,0,3077131718,0,1786,0,93790632975,0,40332290635,0},
{999850004832794,0,131855130,0,1106837550,0,134251026431,0,14505448095,0},
{999591719988030,0,1489732726,0,1318852080,0,400854552839,0,4616874325,0},
{999882128231587,0,42674914485,0,10726252320,0,38215920993,0,26254680615,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999950291528774,0,21327254265,0,184264080,0,23120318050,0,5076634831,0},
{999570454635710,0,896539567,0,0,0,225054318913,0,203594505810,0},
{999678643308303,0,23669811480,0,50908747890,0,244157939572,0,2620192755,0},
{999847363964251,0,3280400075,0,0,0,148809980275,0,545655399,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999927973465266,0,35053320,0,0,0,62787258960,0,9204222454,0},
{999666349685834,0,2189644566,0,186696510,0,330557025205,0,716947885,0},
{999873993431116,0,1236705,0,97181760,0,125067765858,0,840384561,0},
{999894515322080,0,2130023100,0,43303260,0,57790551010,0,45520800550,0},
{1000000000000000,0,0,0,0,0,0,0,0,0},
{999743282172941,0,94595983375,0,76650,0,155360835873,0,6760931161,0},
{999718198948027,0,17761914935,0,10597036905,0,219140906198,0,34301193935,0},
{999911762595931,0,51069560115,0,4949490,0,29532230270,0,7630664194,0},
{999729016236669,0,63973940271,0,0,5005,72711517945,0,134298300110,0}};


long long small_coefficients[17*2 + 1][17 + 1];
long long coefficients[17*3 + 1][17*2 + 1][17 + 1];


long long factorials[20];

int mno(long long x){
	if(x < 10){
		return x;
	}

	long long y = 1;
	while(x > 0 && y > 0){
		y *= (x % 10);
		x /= 10;
	}
	return mno(y);
}

// so, basically, we start with some factor, and we fill in
// the remaining first D digits.
vector<long long> generate_counter(int D, vector<long long> factors){
	int original_size = factors.size();

	vector<long long> RES(10, 0);

	for(int l = 0; l < factors.size(); l++){
		if(factors[l] < 10){
			for(int i = 0; i < 10; i++){
				RES[i] += MAP[D][factors[l]][i];
			}
			factors.erase(factors.begin() + l);
			l--;
			continue;
		}
		if(D == 16){
			vector<long long> vec;
			for(int i = 0; i < 10; i++){
				RES[i] += DEG16[factors[l]][i];
			}
			factors.erase(factors.begin() + l);
			l--;
			continue;
		}
		if(D == 15){
			vector<long long> vec;
			for(int i = 0; i < 10; i++){
				RES[i] += DEG15[factors[l]][i];
			}
			factors.erase(factors.begin() + l);
			l--;
			continue;
		}
	}

	if(factors.size() > 0){
		int amts[3];

		// if we can append any 5 whatsoever, and if the factor is not even.
		if(D >= 1){
			amts[0] = 0;
			amts[1] = 1;
			amts[2] = 0;
			long long v0 = 1;
			long long v1 = 5;
			long long v2 = 1;
			long long v, summand;
			while(true){
				// this is the crux of the algorithm.
				// first assume there is a five somewhere.
				// then adding any 2 will make things 0,
				// so we only have prime factors 3, 5, 7.
				// position 0 is 3, position 1 is 5, position 2 is 7.
				summand = factorials[D]/(factorials[amts[1]]*factorials[amts[2]]*factorials[D-amts[1]-amts[2]]) 
										* small_coefficients[amts[0]][D - amts[1] - amts[2]];
				v = v0 * v1 * v2;
				for(int l = 0; l < factors.size(); l++){
					RES[mno(v * factors[l])] += summand;
				}

				if(amts[0] == 2*(D - amts[1] - amts[2])){
					amts[0] = 0;
					v0 = 1;
				} else {
					amts[0]++;
					v0 *= 3;
					continue;
				}

				if(amts[1] + amts[2] == D){
					amts[1] = 1;
					v1 = 5;
				} else {
					amts[1]++;
					v1 *= 5;
					continue;
				}

				if(amts[2] == D - 1){
					amts[2] = 0;
					v2 = 1;
				} else {
					amts[2]++;
					v2 *= 7;
					continue;
				}

				break;
			}
		}

		amts[0] = 0;
		amts[1] = 0;
		amts[2] = 0;
		long long v0 = 1;
		long long v1 = 1;
		long long v2 = 1;
		long long v, summand;
		while(true){
			// again, this is the crux of the algorithm.
			// we assume there is NO five anywhere.
			// So we only have prime factors 2, 3, 7.
			// position 0 is 2, position 1 is 3, position 2 is 7.
			summand = coefficients[amts[0]][amts[1]][D - amts[2]];

			if(summand > 0){
				summand *= factorials[D] / (factorials[amts[2]] * factorials[D - amts[2]]);
				v = v0 * v1 * v2;
				for(int l = 0; l < factors.size(); l++){
					RES[mno(v * factors[l])] += summand;
				}

				amts[0]++;
				v0 *= 2;
				continue;
			} else {
				amts[0] = 0;
				v0 = 1;
			}

			if(amts[1] == 2*(D - amts[2])){
				amts[1] = 0;
				v1 = 1;
			} else {
				amts[1]++;
				v1 *= 3;
				continue;
			}

			if(amts[2] == D){
				amts[2] = 0;
				v2 = 1;
			} else {
				amts[2]++;
				v2 *= 7;
				continue;
			}

			break;
		}
	}

	// all the remaining cases will give us necessarily a 0.
	long long z = original_size;
	for(int i = 0; i < D; i++){
		z *= 10ll;
	}
	for(int i = 0; i < 10; i++){
		z -= RES[i];
	}
	RES[0] += z;

	return RES;
}

void process(){
	long long N;
	cin >> N;
	N++;

	long long x = 1;
	long long leading_digit = 1;
	long long power = 1;
	int degrees = 0;
	vector<long long> counter(10, 0);
	vector<long long> ans(10, 0);
	while(x <= N){
		// we include all of them exclusive of the upper range.
		for(int i = 0; i < 10; i++){
			ans[i] += counter[i];
		}

		if(degrees == 18) break;
		counter = generate_counter(degrees, {leading_digit});
		leading_digit++;
		x += power;
		if(leading_digit == 10){
			leading_digit = 1;
			power *= 10ll;
			degrees++;
		}
	}
	if(leading_digit == 1){
		leading_digit = 9;
		degrees--;
		power /= 10ll;
	}
	x -= power;

	// cout << N << endl;
	// cout << x << endl;

	if(N >= MAX){
		for(long long l = MAX; l < N; l++){
			ans[mno(l)]++;
		}

		for(int i = 0; i < 10; i++){
			cout << ans[i] << ' ';
		}
		cout << '\n';
		return;
	} else {
		power /= 10ll;
	}

	// cout << power << endl;

	// so now we have the following situation: 
	// MAX > N >= x
	// and we wish to calculate for all the numbers up to, but excluding, N.
	// currently, ans calculates for all the numbers up to, but excluding, x.


	vector<long long> digits;
	long long N_copy = N;
	while(N > 0){
		digits.push_back(N%10ll);
		N /= 10ll;
	}
	N = N_copy;

	long long factor = digits.back();
	for(int i = digits.size() - 2; i >= 0; i--){
		// cout << x << endl;
		vector<long long> input;
		if(x <= N){
			// we increase x.
			int upper_range = digits[i];
			if(i != 0 && digits[i - 1] >= 5){
				upper_range = digits[i] + 1;
			}

			for(long long d = 0; d < upper_range; d++){
				input.push_back(factor * d);
			}
			vector<long long> counter = generate_counter(i, input);

			for(int j = 0; j < 10; j++){
				ans[j] += counter[j];
			}

			x += power * upper_range;
		} else {
			// we decrease x.
			int lower_range = digits[i];
			if(i != 0 && digits[i - 1] >= 5){
				lower_range = digits[i] + 1;
			}

			for(long long d = 9; d >= lower_range; d--){
				input.push_back(factor * d);
			}
			vector<long long> counter = generate_counter(i, input);

			for(int j = 0; j < 10; j++){
				ans[j] -= counter[j];
			}

			x -= power * (10ll - lower_range);
			
		}

		factor *= digits[i];
		power /= 10ll;
	}

	for(int i = 0; i < 10; i++){
		cout << ans[i] << ' ';
	}
	cout << '\n';
}

void find_coefficients(){
	// firstly find the small coefficients.
	for(int i = 0; i < 17*2 + 1; i++){
		for(int k = 0; k < 17 + 1; k++){
			small_coefficients[i][k] = 0;

			if(i > 2*k){
				continue;
			}
			long long sum = 0;
			for(int s = max(0, i - k); 2*s <= i; s++){
				// so we have: s nines, i - 2*s threes, and k + s - i ones
				sum += factorials[k]/(factorials[s] * factorials[i - 2*s] * factorials[k + s - i]);
			}
			small_coefficients[i][k] = sum;
			// cout << "i = " << i << "  k = " << k << "  sum = " << sum << endl;
		}
	}
	// cout << "HERE" << endl;

	// and now the big coefficients.
	for(int i = 0; i < 17*3 + 1; i++){
		for(int j = 0; j < 17*2 + 1; j++){
			for(int k = 0; k < 17 + 1; k++){
				// here is how it looks like:
				// there is i factors of 2
				// there is j factors of 3
				// all of them are distributed over k fields.

				coefficients[i][j][k] = 0;
				if(i > 3*k || j > 2*k){
					continue;
				}
				// let a be the amount of number 6, and b the amount of fields in which I place values divisible by 2.
				for(int a = 0; a <= min(min(i, j), k); a++){
					for(int b = 0; b <= k - a; b++){
						if(i - a > 3*b || i - a - b < 0 || j - a > 2*(k - a - b)){
							continue;
						}
						long long val = factorials[k] / factorials[a];
						val /= factorials[b];
						val /= factorials[k - a - b];
						// now I place the values 2, 4, 8 on b fields.
						val *= small_coefficients[i - a - b][b];
						// and finally, I place the values 1, 3, 9 on k - a - b fields.
						val *= small_coefficients[j - a][k - a - b];

						coefficients[i][j][k] += val;
					}
				}
			}
		}
	}
}

// the normal main function

int main(){
	// std::chrono::steady_clock::time_point begin = std::chrono::steady_clock::now();
	cin.tie(NULL);
	ios_base::sync_with_stdio(0);

	factorials[0] = 1;
	for(long long i = 1; i < 20; i++){
		factorials[i] = i * factorials[i - 1];
	}
	find_coefficients();
	// cout << "DONE" << endl;

	int T;
	cin >> T;
	for(int v = 0; v < T; v++){
		process();
	}

	// std::chrono::steady_clock::time_point end = std::chrono::steady_clock::now();
	
	// std::cerr << "Time difference = " << std::chrono::duration_cast<std::chrono::microseconds>(end - begin).count() << "[µs]" << std::endl;
	// std::cerr << "Time difference = " << std::chrono::duration_cast<std::chrono::nanoseconds> (end - begin).count() << "[ns]" << std::endl;
}



// main function used to generate initial MAP values.
/*
int main(){
	cin.tie(NULL);
	ios_base::sync_with_stdio(0);

	factorials[0] = 1;
	for(long long i = 1; i < 20; i++){
		factorials[i] = i * factorials[i - 1];
	}
	find_coefficients();

	int d = 15;
	for(long long factor = 0; factor < 1000; factor++){
		// cout << "d = " << d << " " << "factor = " << factor << endl;
		vector<long long> vec = generate_counter(d, factor);
		cout << "{";

		for(int j = 0; j < 10; j++){
			cout << vec[j];
			if(j != 9){
				cout << ',';
			}
		}
		cout << "}";
		if(factor != 99){
			cout << ",";
		}
		cout << '\n';
	}
}
*/