C.out

Case #1: 9
Case #2: 9
Case #3: 6
Case #4: 12
Case #5: 33
Case #6: 80
Case #7: 56
Case #8: 1000000000
Case #9: 518198
Case #10: 508315
Case #11: 913948
Case #12: 4318266
Case #13: 4032734
Case #14: 400462963
Case #15: 999998019
Case #16: 99991721
Case #17: 99970548
Case #18: 99653800
Case #19: 99275145
Case #20: 99659269
Case #21: 1348416
Case #22: 955943
Case #23: 839004
Case #24: 1711799
Case #25: 867071
Case #26: 1342682
Case #27: 935396
Case #28: 3420797
Case #29: 73144
Case #30: 551313
Case #31: 841901
Case #32: 16602
Case #33: 545906
Case #34: 961455
Case #35: 308482
Case #36: 2533
Case #37: 351198
Case #38: 311271
Case #39: 851
Case #40: 674057
Case #41: 1724
Case #42: 957023
Case #43: 1050323
Case #44: 78
Case #45: 221298
Case #46: 825461
Case #47: 1423
Case #48: 769215
Case #49: 19836
Case #50: 829873
Case #51: 528866
Case #52: 270935
Case #53: 529324
Case #54: 856304
Case #55: 150966
Case #56: 479767
Case #57: 595329
Case #58: 680899
Case #59: 68255
Case #60: 546188
Case #61: 29151
Case #62: 106503
Case #63: 793385
Case #64: 143682
Case #65: 131026
Case #66: 598583
Case #67: 726888
Case #68: 236731
Case #69: 303583
Case #70: 156
Case #71: 4009
Case #72: 494876
Case #73: 80004
Case #74: 5310
Case #75: 866242
Case #76: 621008
Case #77: 584837
Case #78: 790681
Case #79: 184043
Case #80: 5765
Case #81: 700462
Case #82: 964455
Case #83: 2608
Case #84: 371202
Case #85: 460887
Case #86: 341482
Case #87: 970
Case #88: 41473
Case #89: 295586
Case #90: 599224
Case #91: 930371
Case #92: 744812
Case #93: 989968
Case #94: 977190
Case #95: 296670
Case #96: 788102
Case #97: 908196
Case #98: 132070
Case #99: 13877
Case #100: 337998
Case #101: 752834
Case #102: 727583
Case #103: 231238
Case #104: 720664
Case #105: 326488
Case #106: 408477
Case #107: 962301
Case #108: 848828
Case #109: 652941
Case #110: 668060
Case #111: 103993
Case #112: 324617
Case #113: 15070