Case #1: 5
Case #2: 2
Case #3: IMPOSSIBLE
Case #4: 5
Case #5: IMPOSSIBLE
Case #6: 11
Case #7: 11459
Case #8: 1592589947
Case #9: 1664421834
Case #10: 42
Case #11: 13
Case #12: 844511227
Case #13: 433822739
Case #14: 856894040
Case #15: 1615021050
Case #16: 1656791128
Case #17: 5
Case #18: 1641896288
Case #19: 1
Case #20: 1641598580
Case #21: 186
Case #22: 1581738041
Case #23: 31
Case #24: 1720299879
Case #25: 1585245707
Case #26: 565444224
Case #27: 1702977340
Case #28: 59
Case #29: 536967058
Case #30: 13
Case #31: 4
Case #32: 1723997217
Case #33: 1608890495
Case #34: 39884
Case #35: 33802
Case #36: 19586
Case #37: 870123129
Case #38: 12
Case #39: 27