Case 1: 4
Case 2: 35
Case 3: 106
Case 4: 4960
Case 5: 7581457339
Case 6: 13295518302
Case 7: 17271359114
Case 8: 25048183778
Case 9: 39540899729
Case 10: 44416033888
Case 11: 49567174067
Case 12: 60669388955
Case 13: 73683901760
Case 14: 81519270472
Case 15: 82809243176
Case 16: 82309917979
Case 17: 79312445221
Case 18: 82894114297
Case 19: 82837637106
Case 20: 85482305076
Case 21: 86891777886
Case 22: 82352950907
Case 23: 81088913938
Case 24: 85289549070
Case 25: 74554957005