Time Limit: 5000/1000 MS (Java/Others)

Memory Limit: 32768/32768 K (Java/Others)

What a nice day! The sky is blue, and the sea is calm. It is a day that is suitable for marine navigation training. A training ship of a Naval Training School sails out from the naval port and arrives at a sea area. The navigation instructor is not only an expert in navigation but also an amateur mathematician. The instructor gives the practice assignment as soon as the first student stands at the position of the navigator: First, navigates 1 nautical mile to the east, and then 2 nautical miles to the south, finally 4 nautical miles to the west, and stops at a certain place. The first student accomplishes the task successfully. Then the second student takes the place, and the instructor gives him a new practice assignment: Firstly, navigates 1 nautical mile to the east, then 2 nautical miles to the south, and then 3 nautical miles to the west, finally 3 nautical miles to the north, and stops at a fixed place. Just like this, the students drive the training ship to accomplish the assignment one by one. There is a student who is interested in numbers and taking records. He writes down the first sequence 1, 2, and 4 as soon as the first student accepts the assignment. Later, he writes down the second sequence1, 2, 3, and 6 when the second student accepts the assignment. As a mathematic lover, the student always connects the numbers to some mathematic problems. When he writes down the first sequence, 1, 2, and 4, he figures out that every number in the sequence is the divisors of 4, and 4 is also the last number in the sequence. When he writes down the second sequence1, 2, 3 and 6, he also figures out that every number in the sequence is the divisors of 6, and 6 is also the last number in the sequence. After all the students have finished the assignment, the student looks at the record and comes to the conclusion followed: There is one thing in common for the assignments that the instructor has given to the students, that is, take the direction turning point as the gap, and the sailing distance in all directions form a sequence, every number in the sequence is the divisor of the last one.

The marine navigation training finishes. On the way back, the students have a good time, singing, talking, laughing, and appreciating the sea scenery. The student shows the instructor the records and tells him his findings. The instructor laughs and says to the student, “Well done! You like taking records and thinking, and then finding out something from it. It is a good habit, and also a scientific habit.” The instructor then continues, “Just like science does not have limit, the scientific questions do not have limit, either. The question we have just discussed will not end, and we can also pose new questions.”

The following is the new question the instructor raises:

First, we give a new definition: For a positive integer, if it has K different divisors, then it is called a K- dimension number.

For instance, the positive integer 4 has three divisors, 1, 2and 4, so 4 is a 3- dimension number. The positive integer 6 has four divisors, 1, 2, 3and 6, so 6 is a 4- dimension number.

Now a question is posed: how to work out the nth K-dimension number? (n<10000，Kmax<=100,here Kmax is the greatest prime divisor of K).And you can assume if K is a k-dimension number, it doesn't exceed 3-dimension.

For example, if it is required to work out the second 3-dimension number, that is to say when n=2, K=3, then the answer is 9. Because 4 is the first 3-dimension number, and 9 has three common divisors 1, 3 and 9. Therefore, 9 is the second 3-dimension number.

The student thinks: if n and K are small enough, we can work out easily. Otherwise, we have to turn to the computer for n and K are too big to deal with.

He begins to think it over on the ship.

The marine navigation training finishes. On the way back, the students have a good time, singing, talking, laughing, and appreciating the sea scenery. The student shows the instructor the records and tells him his findings. The instructor laughs and says to the student, “Well done! You like taking records and thinking, and then finding out something from it. It is a good habit, and also a scientific habit.” The instructor then continues, “Just like science does not have limit, the scientific questions do not have limit, either. The question we have just discussed will not end, and we can also pose new questions.”

The following is the new question the instructor raises:

First, we give a new definition: For a positive integer, if it has K different divisors, then it is called a K- dimension number.

For instance, the positive integer 4 has three divisors, 1, 2and 4, so 4 is a 3- dimension number. The positive integer 6 has four divisors, 1, 2, 3and 6, so 6 is a 4- dimension number.

Now a question is posed: how to work out the nth K-dimension number? (n<10000，Kmax<=100,here Kmax is the greatest prime divisor of K).And you can assume if K is a k-dimension number, it doesn't exceed 3-dimension.

For example, if it is required to work out the second 3-dimension number, that is to say when n=2, K=3, then the answer is 9. Because 4 is the first 3-dimension number, and 9 has three common divisors 1, 3 and 9. Therefore, 9 is the second 3-dimension number.

The student thinks: if n and K are small enough, we can work out easily. Otherwise, we have to turn to the computer for n and K are too big to deal with.

He begins to think it over on the ship.

提交代码