Labyrinth Number Maze

During the summer vacation, Qianlian plans to build a castle by her private beach and an underground maze beneath it. The maze is abstracted as a directed graph with n vertices and a total of n*m edges. Every vertex has exactly m outgoing edges, which are labeled with consecutive integers from 0 to m-1. Vertex 1 is the unique entrance as well as the unique exit. The design has a unique twist: if you record the sequence of edge labels along any path starting at vertex 1, you obtain an m-ary number (possibly with leading zeros). In fact, every such m-ary number corresponds to exactly one path starting from vertex 1.

Qianlian has chosen an integer K and wishes to design the maze so that a path starting from vertex 1 returns to vertex 1 if and only if the m-ary number formed by its edge labels is a multiple of K. It turns out that for some choices of m and K, such a maze design is impossible for every n. Therefore, given m and K, Qianlian is interested in finding the smallest positive integer n for which a maze satisfying the above conditions exists.

Note: The natural construction for checking divisibility by K is to simulate an automaton that computes the remainder of an m-ary number modulo K. The standard automaton for this task has exactly K states (with state 0 representing divisibility by K). By a simple translation of labels (relabeling state 0 as 1), one immediately obtains a valid maze with n = K vertices. It can be shown that K is the minimum possible number under these constraints.

inputFormat

The input consists of two integers m and K separated by a space.

outputFormat

Output a single integer representing the minimum number of vertices n for designing a maze that satisfies the condition: a path starting from vertex 1 returns to vertex 1 if and only if the corresponding m-ary number is a multiple of K.

sample

10 3

3