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:

Các lệnh

* ~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~).

Chấm Điểm

Gọi ~x~ là ~min~ số lệnh của từng case bạn dùng trong một test.

• Nếu ~5 \le x \le 7~, bạn nhận được ~30\%~ điểm của test đó.
• Nếu ~x = 4~, bạn nhận được ~70\%~ điểm của test đó.
• Nếu ~x~ nhỏ hơn ~4~, 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 ~x~ 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.

Interaction

Với mỗi test case, quá trình tương tác bắt đầu bằng việc đọc số nguyên ~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:

• ~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.

• ~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.

• ~div~ ~y~: chia ~x~ cho số nguyên dương ~y~ (~1 \le y \le 10^{18}~).
  Jury trả ~1~ nếu ~y~ chia hết ~x~ (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.

• ~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 phân biệt hoa/thường.

Trả lời

Khi bạn tin rằng ~x = n~, in ra:

• ~!~

Jury sẽ trả:

• ~1~ nếu ~x~ đúng bằng ~n~,
• ~-1~ nếu không đúng.

Lệnh ~!~ không tính vào giới hạn ~7~ lệnh.

Lỗi và kết thúc

• Nếu bạn dùng hơn ~7~ lệnh cho một test case, hoặc in ra lệnh không hợp lệ, jury sẽ trả ~-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 Wrong Answer.

Flush output

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ị Idleness limit exceeded.

Ví dụ:

• C/C++: ~fflush(stdout)~ hoặc ~cout.flush()~
• Java: ~System.out.flush()~
• Python: ~sys.stdout.flush()~
• Rust: ~std::io::stdout().flush()~

Ghi chú

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.

Người ngoài hành tinh quyết định tới thăm các em học sinh của HNAms. Tuy nhiên vì ngôn ngữ bất đồng nên các em không hiểu những người ngoài hành tinh muốn nói gì. Vì vậy các em phải mang theo từ điển của mình ra để cho họ xem. Sau đó các em sẽ đoán xem là họ muốn nói đến từ nào trong từ điển. Từ điển cũng chỉ gồm ~26~ chữ cái thường từ ~a~ đến ~z~. Tuy nhiên vì không thể giải thích được với nhau nên hiện tại bước đầu giao tiếp vẫn là đoán từ và các câu hỏi để đoán từ phải vô cùng đơn giản. Người ngoài hành tinh chỉ có thể hiểu các câu hỏi sau:

1. Có bao nhiêu kí tự ~C~ trong từ đó?
2. Kí tự tại vị trí ~X~ là kí tự gì?

Nhiệm vụ của các bạn là viết một chương trình, sử dụng các câu lệnh được cung cấp để thực hiện khảo sát từ điển trong một bộ dữ liệu vào và đưa ra từ mà người ngoài hành tinh muốn nói là từ gì.

Input

• Dòng đầu tiên là số nguyên dương ~N~ (~1 \le N \le 10^6~) là số từ trong từ điển.
• ~N~ dòng tiếp theo mô tả từ điển chỉ gồm danh sách các từ đôi một khác nhau, trong đó mỗi từ nằm trên một dòng và chỉ gồm các chữ cái in thường từ ~a~ đến ~z~ dài tối đa ~50~ kí 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à em đọ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 lệnh được sử dụng:

• count c (~c~ là một kí tự bất kì từ a đến z): máy sẽ in ra số lượng kí tự c trong từ cần tìm. Chi phí sử dụng hàm count c 1 lần là 1 đơn vị.
• getpos x (~x~ là một số nguyên dương): máy sẽ in ra kí tự tại vị trí x trong từ cần tìm (từ trái sang phải, xâu được đánh số từ 1). Nếu ~x~ lớn hơn độ dài của từ, máy sẽ in ra kí tự #. Chi phí sử dụng hàm getpos x 1 lần là 10 đơn vị.
• answer s (~s~ là một xâu kí tự): là từ mà em đã xác định được. Chi phí sử dụng thủ tục answer() là 0 đơn vị. Chương trình bắt buộc phải gọi thủ tục answer() 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 gọi thủ tục answer() với đáp án không chính xác, chạy quá thời gian quy định, sử dụng quá 1000 đơn vị 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 chi phí bạn sử dụng tăng lên.

Sample Input 1

7
cat
can
mic
man
tiger
hello
world

Sample Output 1

Giả sử từ người ngoài hành tinh muốn nói là cat. Các hoạt động nhập xuất có thể diễn ra như sau:

>> getpos 4
<< #
>> count c
<< 1
>> count a
<< 1
>> count n
<< 0
>> answer cat

Explaination

• Độ dài của từ cat là ~3~ nên khi hỏi độ dài bằng ~4~ vượt quá độ dài ~3~, máy in ra dấu #
• Trong từ cat có 1 kí tự c nên máy in ra ~1~
• Trong từ cat có 1 kí tự a nên máy in ra ~1~
• Trong từ cat không có kí tự n nên máy in ra ~0~
• Như vậy bạn đã trả lời đúng với chi phí sử dụng là ~13~. Chương trình khi in ra answer cat sẽ đưa đáp án đồng thời thoát chương trình chạy của bạn.

Có ~n~ khu vực dân cư, khu vực ~i~ ở vị trí ~(x_i,y_i)~. Người ta muốn đặt ~k~ siêu thị để cung cấp hàng hóa cho ~n~ khu vực dân cư này. Người dân ở khu vực dân cư ~i~ khi mua hàng sẽ chọn siêu thị gần nhát, do đó tiêu chí đánh giá việc đặt ~k~ siêu thị dựa trên giá trị: tổng khoảng cách của từng khu vực dân cư đến siêu thị gần nhất, giá trị này càng nhỏ càng thể hiện việc chọn là tối ưu.

Yêu cầu: Cho ~n,k~ và tọa độ của ~n~ khu dân cư. Hãy xác định vị trí đặt ~k~ siêu thị để tổng các khoảng cách của từng khu vực dân cư đến siêu thị gần nhất càng nhỏ càng tốt.

Input

• Dòng đầu chứa hai số nguyên ~n,k~ (~k \le n~).
• ~n~ dòng sau, mỗi dòng chứa hai số thực ~x_i,y_i~ (~0 \le x_i,y_i \le 10000~).

Output

• Gồm ~k~ dòng, mỗi dòng chứa hai số thực là tọa độ của các siêu thị.

Scoring

• Subtask ~1~ (~50\%~ số điểm): ~n \le 15~.
• Subtask ~2~ (~50\%~ số điểm): ~n \le 5000~.
• Cách tính điểm: Với mỗi test, gọi tổng khoảng cách theo phương án của giám khảo là ~res~, gọi tổng khoảng cách theo phương án của thí sinh là ~ans~, điểm số tính theo công thức sau: ~min(1,(\frac{res}{ans}))^2~.

Sample Input 1

5 2
0 0
1 0
1 1
0 1
9 9

Sample Output 1

0.5 0.5
9 9

Cho một dãy ~p_1,p_2,...,p_n~ là một hoán vị của ~1,2,...,n~. Bạn được thực hiện hai phép biến đổi sau:

• Chọn hai phần tử bất kì và tráo đổi,loại phép biến đổi này chỉ được thực hiện nhiều nhất một lần.
• Chọn hai phần tử kề nhau và tráo đổi, loại phép biến đổi này được thực hiện nhiều lần.

Yêu cầu: Tính số phép biến đổi ít nhất để đưa dãy hoán vị ~p_1,p_2,...,p_n~ về dãy hoán vị ~1,2,3...,n~.

Input

• Dòng đầu tiên chứa số nguyên dương ~n~.
• Dòng thứ hai gồm ~n~ số nguyên dương ~p_1,p_2,...,p_n~.

Output

• In ra số bước ít nhất để đưa dãy ~p~ về hoán vị ~1,2,3,...,n~.

Constraints .

• ~1 \le N \le 10^5~.

Subtask

• Sub ~1~ ~(10\%)~: ~n = 3~.
• Sub ~2~ ~(20\%)~: ~n \le 30~.
• Sub ~3~ ~(20\%)~: ~n \le 300~.
• Sub ~4~ ~(20\%)~: ~n \le 1000~.
• Sub ~5~ ~(15\%)~: ~n \le 10^4~.
• Sub ~6~ ~(15\%)~: ~n \le 10^5~.

Sample Input 1

5
5 3 4 2 1

Sample Output 1

3