Case 1: 100 -1
Case 2: 100 2
Case 3: 100 4
Case 4: 64138204 44087568
Case 5: 739967369 573538319
Case 6: 667489294 292860900
Case 7: 10000 1
Case 8: 10000 2
Case 9: 10000 2
Case 10: 10000 -1
Case 11: 1000000 16
Case 12: 1000000 1
Case 13: 1000000 2
Case 14: 1000000 -1
Case 15: 1000000 2
Case 16: 1000000 1
Case 17: 1000000 1
Case 18: 1000000 1
Case 19: 1000000 4
Case 20: 1000000 543872
Case 21: 1000000 869184
Case 22: 1000000 68608
Case 23: 1000000 -1
Case 24: 1000000 9702
Case 25: 1000000 29
Case 26: 1000000 1328
Case 27: 1000000 360
Case 28: 1000000 -1
Case 29: 1000000 10
Case 30: 1000000 30
Case 31: 1000000 12
Case 32: 1000000 3936
Case 33: 1000000 180
Case 34: 1000000 36
Case 35: 1000000 2
Case 36: 1000000 40