Let’s play a game. There are n people who think of a random number. They don’t know the rules of the game. Only you do. You know that at each step of the game, the people who have kept a number with the least number of divisors, get out of the game. You ask everyone their numbers and then you should tell who’s going to leave the game on each step. They should guess the rule of the game. Now your task is to write a program that simulates the game and prints the names of people who’ll leave the game at each step.
The first line of the input contains a single integer n which is the number of people participating in the game. The next n lines contain the names of participants and the number they’ve memorized. It’s guaranteed that the names are unique and the numbers are positive.
The program should print the name of people leaving the game at each stage of the game.