As punishment for attacking Sunland, Wet Shark is now forced to walk on a line of numbered squares, starting from and going to infinity. Wet Shark initially has a strength of . To make the experience harder for Wet Shark, each square that has a label divisible by and/or but not divisible by contains a black glob of jelly, stepping on which his strength decreases by .

Wet Shark does not know that this line of squares is infinitely long, and he is determined to continue walking until his strength reaches . Wet Shark walks from square to square, so he starts at square , goes to square , then , then , etc.

Wet Shark’s punisher needs your help, and wants to compute where Wet Shark will stop in order to meet him there and punish him. Given Wet Shark’s initial strength , find the square on which Wet Shark’s strength will reach . Wet Shark can go far if defenses are not strong enough, so please output the answer modulo . Wet Shark is curious, so he wants to know that given strength initially, how far he will go for different values . Help him figure out how long he can go without doom for each .