Trong bài toán này, có một số nguyên chưa biết ~x~ với ~1 \le x \le 10^9~. Nhiệm vụ của bạn là biến nó thành số nguyên ~n~ được cho trong input. Bằng cách sử dụng một CPU, bạn có thể gửi lệnh để thực hiện một trong các thao tác sau:

Trong đó, ~S(n)~ là hàm trả về tổng các chữ số của số nguyên không âm ~n~. Ví dụ: ~S(123) = 1 + 2 + 3 = 6~.

Bạn phải biến ~x~ thành ~n~ với càng ít thao tác càng tốt.

Input

Mỗi input gồm nhiều test case:

• Dòng đầu chứa số nguyên ~t~ (~1 \le t \le 100~) — số lượng test case.

• Mỗi test case gồm một dòng chứa một số nguyên ~n~ (~1 \le n \le 10^9~).

Interaction

Bạn có thể sử dụng không quá ~7~ lệnh với CPU để biến đổi từ ~x~ thành ~n~. Để gửi lệnh, bạn in ra một dòng theo đúng định dạng của một trong các lệnh sau:

• ~\texttt{add}~ ~y~: cộng số nguyên ~y~ (~-10^{18} \le y \le 10^{18}~) vào ~x~. Jury trả ~1~ nếu ~x + y~ nằm trong ~[1, 10^{18}]~ (thành công), và khi đó cập nhật ~x \leftarrow x + y~. Nếu không, trả ~0~ và ~x~ không đổi.

• ~\texttt{mul}~ ~y~: nhân ~x~ với số nguyên dương ~y~ (~1 \le y \le 10^{18}~). Jury trả ~1~ nếu ~x \cdot y~ nằm trong ~[1, 10^{18}]~ (thành công), và khi đó cập nhật ~x \leftarrow x \cdot y~. Nếu không, trả ~0~ và ~x~ không đổi.

• ~\texttt{div}~ ~y~: chia ~x~ cho số nguyên dương ~y~ (~1 \le y \le 10^{18}~). Jury trả ~1~ nếu ~x~ chia hết cho ~y~ (thành công), và khi đó cập nhật ~x \leftarrow \frac{x}{y}~. Nếu không, trả ~0~ và ~x~ không đổi.

• ~\texttt{digit}~: thay ~x~ bằng tổng chữ số của nó. Jury luôn trả ~1~ và cập nhật ~x \leftarrow S(x)~.

Lưu ý, lệnh có phân biệt chữ hoa/thường.

Khi bạn tin rằng ~x = n~, in ra ~!~. Jury sẽ trả ~1~ nếu ~x~ đúng bằng ~n~, và ~-1~ nếu ngược lại. Lệnh ~!~ không tính vào giới hạn ~7~ lệnh.

Sau mỗi lần in lệnh, bạn phải xuống dòng và flush output, nếu không sẽ bị ~\texttt{Idleness limit exceeded}~. Để flush output, dùng:

• fflush(stdout) hoặc cout.flush() với C++.

• System.out.flush() với Java.

• sys.stdout.flush() với Python.

• std::io::stdout().flush() với Rust.

• Với các ngôn ngữ khác, vui lòng tham khảo documentation.

Nếu chương trình của bạn dùng quá ~7~ lệnh cho một test case, hoặc in ra lệnh không hợp lệ, jury sẽ trả ra ~-1~. Sau khi nhận ~-1~, chương trình của bạn phải kết thúc ngay lập tức để nhận verdict ~\texttt{Wrong Answer}~. Ngược lại, bạn có thể nhận bất kì verdict nào.

Interactor là non-adaptive: số nguyên bí mật ~x~ không thay đổi trong suốt quá trình tương tác.

Scoring

Gọi ~\tau~ là số lệnh lớn nhất của từng case bạn dùng trong một test:

• Nếu ~5 \le \tau \le 7~, bạn nhận được ~30\%~ điểm của test đó.

• Nếu ~\tau = 4~, bạn nhận được ~70\%~ điểm của test đó.

• Nếu ~\tau<4~, số lệnh của bạn sẽ được so sánh với số lệnh của ban giám khảo, nếu ~\tau~ không lớn hơn giá trị của ban giám khảo, bạn nhận được toàn bộ số điểm, ngược lại nhận được ~90\%~ điểm của test.

Sample Input 1

3
9

1

0

1

1

67

1

1

420

-1

Sample Output 1

div 2

mul 1000000000000000000

digit

!

add -2

!

!

Notes

Lưu ý dòng trống trong ví dụ chỉ để giúp cho người đọc dễ quan sát, và sẽ không xuất hiện trong quá trình tương tác thực tế.