input
2
7 3 2
8 2 5
2
1 7 3 5
2 7 1 8 2 10
0
0
5
7 5 111
3 5 222
2 5 333
9 5 444
1 5 555
0
5
641 5 50
262 5 114
83 5 21
24 5 79
105 5 75
4
1 641 1 46
1 262 2 200
1 83 3 55
2 24 1 105 2 205
4
81 1 27
62 2 135
113 3 27
34 4 56
4
2 81 1 62 1 149
2 62 1 113 1 147
2 113 1 34 1 77
2 81 1 34 1 75

4
271 3 103
112 3 92
173 3 114
155 3 87
10
1 155 2 150
2 173 1 155 1 177
1 173 2 212
2 112 1 155 1 152
2 112 1 173 1 190
1 112 2 169
2 271 1 155 1 165
2 271 1 173 1 195
2 271 1 112 1 177
1 271 2 181
3
51 3 24
62 3 38
43 3 12
53
1 43 1 10
1 43 2 21
1 43 3 31
1 62 1 32
2 62 1 43 1 43
2 62 1 43 2 57
2 62 1 43 3 64
1 62 2 68
2 62 2 43 1 82
2 62 2 43 2 85
2 62 2 43 3 99
1 62 3 103
2 62 3 43 1 107
2 62 3 43 2 119
2 62 3 43 3 132
1 51 1 22
2 51 1 43 1 33
2 51 1 43 2 44
2 51 1 43 3 52
2 51 1 62 1 55
3 51 1 62 1 43 1 67
3 51 1 62 1 43 2 77
3 51 1 62 1 43 3 84
2 51 1 62 2 94
3 51 1 62 2 43 1 103
3 51 1 62 2 43 2 107
3 51 1 62 2 43 3 126
2 51 1 62 3 124
3 51 1 62 3 43 1 132
3 51 1 62 3 43 2 152
1 51 2 41
2 51 2 43 1 55
2 51 2 43 2 67
2 51 2 43 3 77
2 51 2 62 1 78
3 51 2 62 1 43 1 87
3 51 2 62 1 43 2 94
3 51 2 62 1 43 3 115
2 51 2 62 2 110
3 51 2 62 2 43 1 125
3 51 2 62 2 43 2 138
2 51 2 62 3 152
3 51 2 62 3 43 1 151
1 51 3 62
2 51 3 43 1 72
2 51 3 43 2 84
2 51 3 43 3 92
2 51 3 62 1 102
3 51 3 62 1 43 1 104
3 51 3 62 1 43 2 117
2 51 3 62 2 127
3 51 3 62 2 43 1 142
2 51 3 62 3 158
4
21 4 107
52 4 183
43 4 126
64 4 150
68
2 43 2 64 4 767
2 43 3 64 3 753
2 43 4 64 2 740
3 52 1 43 1 64 4 773
3 52 1 43 2 64 3 823
3 52 1 43 3 64 2 749
3 52 1 43 4 64 1 762
2 52 2 64 4 889
3 52 2 43 1 64 3 820
3 52 2 43 2 64 2 854
3 52 2 43 3 64 1 796
2 52 2 43 4 783
2 52 3 64 3 939
3 52 3 43 1 64 2 916
3 52 3 43 2 64 1 827
2 52 3 43 3 806
2 52 4 64 2 918
3 52 4 43 1 64 1 917
2 52 4 43 2 836
3 21 1 43 1 64 4 758
3 21 1 43 2 64 3 736
3 21 1 43 3 64 2 691
3 21 1 43 4 64 1 647
3 21 1 52 1 64 4 801
4 21 1 52 1 43 1 64 3 805
4 21 1 52 1 43 2 64 2 766
4 21 1 52 1 43 3 64 1 744
3 21 1 52 1 43 4 675
3 21 1 52 2 64 3 840
4 21 1 52 2 43 1 64 2 782
4 21 1 52 2 43 2 64 1 805
3 21 1 52 2 43 3 766
3 21 1 52 3 64 2 860
4 21 1 52 3 43 1 64 1 876
3 21 1 52 3 43 2 781
3 21 1 52 4 64 1 880
3 21 1 52 4 43 1 869
2 21 2 64 4 733
3 21 2 43 1 64 3 719
3 21 2 43 2 64 2 689
3 21 2 43 3 64 1 660
2 21 2 43 4 661
3 21 2 52 1 64 3 745
4 21 2 52 1 43 1 64 2 765
4 21 2 52 1 43 2 64 1 687
3 21 2 52 1 43 3 697
3 21 2 52 2 64 2 801
4 21 2 52 2 43 1 64 1 728
3 21 2 52 2 43 2 732
3 21 2 52 3 64 1 858
3 21 2 52 3 43 1 765
2 21 2 52 4 880
2 21 3 64 3 663
3 21 3 43 1 64 2 680
3 21 3 43 2 64 1 622
2 21 3 43 3 657
3 21 3 52 1 64 2 748
4 21 3 52 1 43 1 64 1 686
3 21 3 52 1 43 2 680
3 21 3 52 2 64 1 737
3 21 3 52 2 43 1 724
2 21 3 52 3 748
2 21 4 64 2 641
3 21 4 43 1 64 1 620
2 21 4 43 2 612
3 21 4 52 1 64 1 693
3 21 4 52 1 43 1 634
2 21 4 52 2 715
5
31 5 120
52 5 107
23 5 148
64 5 171
55 5 133
55
1 55 1 116
1 55 2 237
1 55 3 363
1 64 1 154
2 64 1 55 1 264
2 64 1 55 2 385
1 64 2 315
2 64 2 55 1 408
1 64 3 467
1 23 1 133
2 23 1 55 1 253
2 23 1 55 2 360
2 23 1 64 1 297
3 23 1 64 1 55 1 420
2 23 1 64 2 446
1 23 2 275
2 23 2 55 1 369
2 23 2 64 1 406
1 23 3 404
1 52 1 93
2 52 1 55 1 209
2 52 1 55 2 328
2 52 1 64 1 247
3 52 1 64 1 55 1 374
2 52 1 64 2 386
2 52 1 23 1 232
3 52 1 23 1 55 1 361
3 52 1 23 1 64 1 396
2 52 1 23 2 355
1 52 2 199
2 52 2 55 1 326
2 52 2 64 1 343
2 52 2 23 1 319
1 52 3 295
1 31 1 102
2 31 1 55 1 215
2 31 1 55 2 355
2 31 1 64 1 259
3 31 1 64 1 55 1 377
2 31 1 64 2 425
2 31 1 23 1 230
3 31 1 23 1 55 1 361
3 31 1 23 1 64 1 382
2 31 1 23 2 358
2 31 1 52 1 202
3 31 1 52 1 55 1 310
3 31 1 52 1 64 1 358
3 31 1 52 1 23 1 334
2 31 1 52 2 297
1 31 2 211
2 31 2 55 1 339
2 31 2 64 1 366
2 31 2 23 1 338
2 31 2 52 1 302
1 31 3 320
5
51 5 202
72 5 185
63 5 110
94 5 147
25 5 199
95
1 25 1 183
1 25 2 354
1 25 3 549
1 25 4 748
1 25 5 915
1 94 1 126
2 94 1 25 1 318
2 94 1 25 2 463
2 94 1 25 3 662
1 94 2 276
2 94 2 25 1 429
2 94 2 25 2 602
1 94 3 401
2 94 3 25 1 557
1 94 4 512
1 94 5 625
1 63 1 99
2 63 1 25 1 284
2 63 1 25 2 462
2 63 1 25 3 650
2 63 1 94 1 218
3 63 1 94 1 25 1 424
2 63 1 94 2 343
2 63 1 94 3 490
1 63 2 207
2 63 2 25 1 385
2 63 2 25 2 575
2 63 2 94 1 327
2 63 2 94 2 478
1 63 3 284
2 63 3 25 1 466
2 63 3 94 1 448
1 63 4 405
1 63 5 517
1 72 1 159
2 72 1 25 1 342
2 72 1 25 2 496
2 72 1 25 3 704
2 72 1 94 1 286
3 72 1 94 1 25 1 489
2 72 1 94 2 412
2 72 1 94 3 570
2 72 1 63 1 277
3 72 1 63 1 25 1 420
3 72 1 63 1 94 1 411
2 72 1 63 2 348
2 72 1 63 3 438
1 72 2 315
2 72 2 25 1 518
2 72 2 25 2 660
2 72 2 94 1 450
2 72 2 94 2 618
2 72 2 63 1 432
2 72 2 63 2 537
1 72 3 472
2 72 3 25 1 686
2 72 3 94 1 632
2 72 3 63 1 605
1 72 4 688
1 72 5 805
1 51 1 190
2 51 1 25 1 373
2 51 1 25 2 540
2 51 1 25 3 727
2 51 1 94 1 304
3 51 1 94 1 25 1 477
2 51 1 94 2 446
2 51 1 94 3 547
2 51 1 63 1 278
3 51 1 63 1 25 1 460
3 51 1 63 1 94 1 404
2 51 1 63 2 392
2 51 1 63 3 473
2 51 1 72 1 337
3 51 1 72 1 25 1 551
3 51 1 72 1 94 1 502
3 51 1 72 1 63 1 467
2 51 1 72 2 526
2 51 1 72 3 643
1 51 2 380
2 51 2 25 1 525
2 51 2 25 2 754
2 51 2 94 1 490
2 51 2 94 2 656
2 51 2 63 1 463
2 51 2 63 2 549
2 51 2 72 1 512
2 51 2 72 2 666
1 51 3 570
2 51 3 25 1 700
2 51 3 94 1 663
2 51 3 63 1 652
2 51 3 72 1 728
1 51 4 711
1 51 5 889
5
101 5 406
82 5 320
73 5 375
54 5 291
45 5 178
81
3 73 1 54 1 45 3 1116
3 73 1 54 2 45 2 1116
3 73 1 54 3 45 1 1212
3 73 2 54 1 45 2 1229
3 73 2 54 2 45 1 1314
3 73 3 54 1 45 1 1498
3 82 1 54 1 45 3 996
3 82 1 54 2 45 2 1157
3 82 1 54 3 45 1 1234
3 82 1 73 1 45 3 1082
4 82 1 73 1 54 1 45 2 1261
4 82 1 73 1 54 2 45 1 1237
3 82 1 73 1 54 3 1364
3 82 1 73 2 45 2 1212
4 82 1 73 2 54 1 45 1 1385
3 82 1 73 2 54 2 1520
3 82 1 73 3 45 1 1428
3 82 1 73 3 54 1 1614
3 82 2 54 1 45 2 1107
3 82 2 54 2 45 1 1260
3 82 2 73 1 45 2 1220
4 82 2 73 1 54 1 45 1 1395
3 82 2 73 1 54 2 1405
3 82 2 73 2 45 1 1443
3 82 2 73 2 54 1 1479
3 82 3 54 1 45 1 1272
3 82 3 73 1 45 1 1301
3 82 3 73 1 54 1 1382
3 101 1 54 1 45 3 1046
3 101 1 54 2 45 2 1169
3 101 1 54 3 45 1 1326
3 101 1 73 1 45 3 1236
4 101 1 73 1 54 1 45 2 1285
4 101 1 73 1 54 2 45 1 1387
3 101 1 73 1 54 3 1456
3 101 1 73 2 45 2 1391
4 101 1 73 2 54 1 45 1 1398
3 101 1 73 2 54 2 1529
3 101 1 73 3 45 1 1521
3 101 1 73 3 54 1 1658
3 101 1 82 1 45 3 1121
4 101 1 82 1 54 1 45 2 1291
4 101 1 82 1 54 2 45 1 1397
3 101 1 82 1 54 3 1487
4 101 1 82 1 73 1 45 2 1326
5 101 1 82 1 73 1 54 1 45 1 1429
4 101 1 82 1 73 1 54 2 1447
4 101 1 82 1 73 2 45 1 1522
4 101 1 82 1 73 2 54 1 1537
3 101 1 82 1 73 3 1610
3 101 1 82 2 45 2 1234
4 101 1 82 2 54 1 45 1 1424
3 101 1 82 2 54 2 1498
4 101 1 82 2 73 1 45 1 1359
4 101 1 82 2 73 1 54 1 1507
3 101 1 82 2 73 2 1580
3 101 1 82 3 45 1 1451
3 101 1 82 3 54 1 1475
3 101 1 82 3 73 1 1567
3 101 2 54 1 45 2 1255
3 101 2 54 2 45 1 1431
3 101 2 73 1 45 2 1420
4 101 2 73 1 54 1 45 1 1524
3 101 2 73 1 54 2 1539
3 101 2 73 2 45 1 1479
3 101 2 73 2 54 1 1649
3 101 2 82 1 45 2 1295
4 101 2 82 1 54 1 45 1 1457
3 101 2 82 1 54 2 1525
4 101 2 82 1 73 1 45 1 1533
4 101 2 82 1 73 1 54 1 1690
3 101 2 82 1 73 2 1656
3 101 2 82 2 45 1 1402
3 101 2 82 2 54 1 1482
3 101 2 82 2 73 1 1663
3 101 3 54 1 45 1 1569
3 101 3 73 1 45 1 1576
3 101 3 73 1 54 1 1714
3 101 3 82 1 45 1 1527
3 101 3 82 1 54 1 1555
3 101 3 82 1 73 1 1626

output
14
0
8325
1563
558
1041
188
2001
2916
3602
6672