Ugly numbers are numbers whose only prime factors are 2, 3 or 5. The sequence

1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ...

shows the first 11 ugly numbers. By convention, 1 is included.

Write a program to find and print the 1500’th ugly number.

Input

There is no input to this program.

Output

Output should consist of a single line as shown below, with ‘<number>’ replaced by the number computed.

Sample Output

The 1500'th ugly number is *<*number*>*.

HINT

使用set来存储副本，判断是否已经存储过。

Accepted

#include<iostream>
#include<set>
#include<queue>
#include<vector>
using namespace std;

typedef long long LL;
const int coeff[3] = { 2,3,5 };

int main()
{
	priority_queue<LL, vector<LL>, greater<LL> >pq;
	set<LL>s;
	pq.push(1);s.insert(1);
	for (int i = 1;;i++) {
		LL x = pq.top();pq.pop();
		if (i == 1500) {
			cout << "The 1500'th ugly number is " << x << "." << endl;
			break;
		}
		for (int j = 0;j < 3;j++) {
			LL x2 = x * coeff[j];
			if (!s.count(x2)) { s.insert(x2);pq.push(x2); }
		}
	}
}