works.ans

Case 1: 44
Case 2: 1116877054
Case 3: 2353506445
Case 4: 10
Case 5: 5009
Case 6: 9909
Case 7: 10
Case 8: 10
Case 9: 11
Case 10: 999999999999999999
Case 11: 87
Case 12: 200
Case 13: 567
Case 14: 87
Case 15: 23
Case 16: 22
Case 17: 10
Case 18: 21
Case 19: 910
Case 20: 47
Case 21: 248
Case 22: 2
Case 23: 819
Case 24: 247203369681152293
Case 25: 2
Case 26: 396800888891632636
Case 27: 826351145
Case 28: 2
Case 29: 2266
Case 30: 726
Case 31: 21156
Case 32: 2856
Case 33: 984166993414
Case 34: 966419538940535230
Case 35: 236999935345
Case 36: 340573421429813701
Case 37: 109901557
Case 38: 770999391876
Case 39: 118371263
Case 40: 999032793419
Case 41: 996837148644712475
Case 42: 2
Case 43: 999987616125
Case 44: 535901345790722483
Case 45: 998934296923945139
Case 46: 7996935188976
Case 47: 533916783647004115
Case 48: 1004095596
Case 49: 1000120001804
Case 50: 999957938912090827