Cô giáo nghĩ trong đầu một số nguyên dương ~X~ trong khoảng từ ~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 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.

Hãy 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 ý hãy flush luồng ra chuẩn sau mỗi dòng được in ra bằng lệnh fflush(stdout) hoặc std::endl trong ngôn ngữ lập trình C++ hoặc các câu lệnh tương ứng ở các ngôn ngữ lập trình khác.

Bạn được phép sử dụng những câu lệnh sau:

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

• traloi x với ~x~ là một số nguyên dương bạn đã xác định được rằng đó là ~X~. 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 bộ dữ liệu, 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 việc dừng chương trình, bài làm sẽ nhận ~0~ điểm cho bộ dữ liệu đó. Số điểm cho mỗi bộ dữ liệu sẽ giảm dần khi số câu hỏi bạn sử dụng tăng lên.

Cụ thể hơn, gọi ~P(Q)~ là số điểm nhận được nếu như đoán đúng sau ~Q~ câu hỏi. Số điểm sẽ được tính như nhau:

$$P(Q) = \begin{cases} 100 & \text{nếu } Q \leq 26000 \\ \left\lfloor 60 + 40 \times \left(\frac{27000-Q}{2000}\right) \right\rfloor & \text{nếu } 26000 < Q \leq 27000 \\ \left\lfloor 30 + 30 \times \left(\frac{80000-Q}{53000}\right) \right\rfloor & \text{nếu } 27000 < Q \leq 80000 \\ \left\lfloor 10 + 20 \times \left(\frac{100000-Q}{920000}\right) \right\rfloor & \text{nếu } 80000 < Q \leq 1000000 \\ 0 & \text{nếu } Q > 1000000 \end{cases}$$

Notes

Giả sử số bí mật là ~4~.