Hôm nay lớp Cam có một trò chơi trong giờ Toán. Cô giáo nghĩ trong đầu một số nguyên \(X\) trong khoảng \(1\) đến \(10^6\). Các bạn học sinh cần tìm được số bí mật X với ít nhất các câu hỏi có dạng: "Ước chung lớn nhất của một số \(X\) với một số \(Y\) là bao nhiêu?". Bạn nào dùng càng ít câu hỏi thì điểm càng cao.

Các bạn hãy giúp cam viết một chương trình, sử dụng các câu lệnh được cung cấp để tìm ra số bí mật \(X\) mà hết ít câu hỏi nhất.

Interaction

• Để tương tác với máy chấm, hãy in mỗi lệnh trên từng dòng. Câu trả lời sẽ được máy chấm in ra trên một dòng khác, và bạn đọc vào. Lưu ý flush luồng ra chuẩn sau mỗi dòng được in ra bằng lệnh fflush(stdout) hoặc cout << endl;

• Các câu lệnh:

• ucln Y (\(Y\) là một số nguyên dương bất kì \(1 \le Y \le 10^{18}\)): máy sẽ in ra ước chung lớn nhất của X và Y.

• traloi x (\(x\) là một số nguyên dương): là số bí mật \(X\) mà bạn đã xác định được. Chương trình bắt buộc phải in ra traloi một lần duy nhất, nếu không sẽ bị \(0\) điểm. Thủ tục này khi được gọi sẽ tự động thoát chương trình bằng câu lệnh exit.

Scoring

• Với mỗi test, nếu chương trình của bạn trả lời với đáp án không chính xác, chạy quá thời gian quy định, sử dụng quá \(1000000\) câu hỏi hoặc gặp các lỗi dẫn tới dừng chương trình, bài làm sẽ nhận 0 điểm cho test đó. Số điểm cho mỗi test sẽ giảm dần khi số câu hỏi bạn sử dụng tăng lên.

Example

• Giả sử số bí mật \(X\) cần tìm là \(300000\), quá trình nhập xuất có thể diễn ra như sau:

  ```
  >> ucln 100000
  << 100000
  >> ucln 200000
  << 100000
  >> ucln 500000
  << 100000
  >> ucln 900000
  << 300000
  >> traloi 300000
  ```