This is the hard version of the problem. In this version, the limit of commands you can send is described in the statement. You can make hacks only if all versions of the problem are solved. This is an interactive problem. Welcome, Duelists! In this interactive challenge, there is an unknown integer (x) ((1 \le x \le 10^9)). You must make it equal to a given integer in the input (n). By harnessing the power of "Mathmech" monsters, you can send a command to do one of the following: Let (f(n)) be the minimum integer such that there is a sequence of (f(n)) commands that transforms (x) into (n) for all (x(1 \le x \le 10^9)). You do not know the value of (x) in advance. Find (f(n)) such that, no matter what (x) is, you can always transform it into (n) using at most (f(n)) commands. Your task is to change (x) into (n) using at most (f(n)) commands. (^{\text{∗}})(S(n)) is a function that returns the sum of all the individual digits of a non-negative integer (n). For example, (S(123) = 1 + 2 + 3 = 6) Each test contains multiple test cases. The first line contains the number of test cases (t) ((1 \le t \le 5000)). The description of the test cases follows. The first and only line of each test case contains one integer (n) ((1 \le n \le 10^9)). The interaction for each test case begins by reading the integer (n). To send a command, output a line in the following format: "add (y)" Add some integer (y) ((-10^{18} \le y \le 10^{18})) to (x). The jury will output "1" if (x + y) is within (1, 10^{18}) ( successful ), and "0" otherwise. If successful, update (x \leftarrow x + y). The jury will output "1" if (x + y) is within (1, 10^{18}) ( successful ), and "0" otherwise. If successful, update (x \leftarrow x + y). "mul (y)" Multiply (x) by a positive integer (y) ((1 \le y \le 10^{18})). The jury will output "1" if