#include <bits/stdc++.h>
#define VERBOSE 0
#define PLUS S[si - 1] += S[si], --si, OP.push_back("+")
#define MULTIPLY S[si - 1] *= S[si], --si, OP.push_back("*")
#define SWAP std::swap(S[si], S[si - 1]), OP.push_back("SWAP")
#define DUP S[si + 1] = S[si], ++si, OP.push_back("DUP")
#define OVER S[si + 1] = S[si - 1], ++si, OP.push_back("OVER")
#define ROT std::swap(S[si], S[si - 2]), std::swap(S[si - 1], S[si - 2]), OP.push_back("ROT")
#define DROP --si, OP.push_back("DROP")
#define MSBL(x_) (uint64_t{1} << (uint64_t{64} - std::countl_zero<uint64_t>(x_) - 1))
uint64_t S[10000];
auto si = 0;
std::vector<std::string> OP;
// Jump assumptions:
// - Stack is [L, 2] when entering
void make_jump2() {
DUP; // [.., 2, 2]
MULTIPLY; // [.., 4]
}
void make_jump3() {
DUP; // [.., 2, 2]
make_jump2(); // [.., 2, 4]
MULTIPLY; // [.., 8]
}
void make_jump4() {
make_jump2(); // [.., 4]
DUP; // [.., 4, 4]
MULTIPLY; // [.., 16]
}
void make_jump5() {
DUP; // [.., 2, 2]
make_jump4(); // [.., 2, 16]
MULTIPLY; // [.., 32]
}
void make_jump6() {
make_jump3(); // [.., 8]
DUP; // [.., 8, 8]
MULTIPLY; // [.., 64]
}
void make_jump7() {
DUP; // [.., 2, 2]
make_jump6(); // [.., 2, 64]
MULTIPLY; // [.., 128]
}
void make_jump8() {
make_jump4(); // [.., 16]
DUP; // [.., 16, 16]
MULTIPLY; // [.., 256]
}
void make_jump9() {
DUP; // [.., 2, 2]
make_jump8(); // [.., 2, 256]
MULTIPLY; // [.., 512]
}
void make_jump10() {
make_jump5(); // [.., 32]
DUP; // [.., 32, 32]
MULTIPLY; // [.., 1024]
}
void make_jump11() {
DUP; // [.., 2, 2]
make_jump10(); // [.., 2, 1024]
MULTIPLY; // [.., 2048]
}
void make_jump12() {
make_jump6(); // [.., 64]
DUP; // [.., 64, 64]
MULTIPLY; // [.., 4096]
}
void make_jump13() {
DUP; // [.., 2, 2]
make_jump12(); // [.., 2, 4096]
MULTIPLY; // [.., 8192]
}
void make_jump14() {
make_jump7(); // [.., 128]
DUP; // [.., 128, 128]
MULTIPLY; // [.., 16384]
}
void make_jump15() {
make_jump5(); // [.., 32]
DUP; // [.., 32, 32]
DUP; // [.., 32, 32, 32]
MULTIPLY; // [.., 32, 1024]
MULTIPLY; // [.., 32768]
}
void make_jump16() {
make_jump8(); // [.., 256]
DUP; // [.., 256, 256]
MULTIPLY; // [.., 65536]
}
void make_jump17() {
DUP; // [.., 2, 2]
make_jump16(); // [.., 2, 65536]
MULTIPLY; // [.., 131072]
}
void make_jump18() {
make_jump9(); // [.., 512]
DUP; // [.., 512, 512]
MULTIPLY; // [.., 262144]
}
void make_jump19() {
DUP; // [.., 2, 2]
make_jump18(); // [.., 2, 262144]
MULTIPLY; // [.., 524288]
}
void print_stack() {
if (VERBOSE) {
for (int i = 0; i <= si; ++i) {
std::cout << S[i] << ' ';
}
std::cout << '\n';
}
}
// Enter with [2, L]
// - go to jmp with [L, 2]
// - retain=false: [L, jmp]
// - retain=true: [2, L, jmp]
void jump(int j, bool retain) {
if (retain) {
OVER; // [2, L, 2]
} else {
SWAP; // [L, 2]
}
switch(j) {
case 2: { make_jump2(); break; }
case 3: { make_jump3(); break; }
case 4: { make_jump4(); break; }
case 5: { make_jump5(); break; }
case 6: { make_jump6(); break; }
case 7: { make_jump7(); break; }
case 8: { make_jump8(); break; }
case 9: { make_jump9(); break; }
case 10: { make_jump10(); break; }
case 11: { make_jump11(); break; }
case 12: { make_jump12(); break; }
case 13: { make_jump13(); break; }
case 14: { make_jump14(); break; }
case 15: { make_jump15(); break; }
case 16: { make_jump16(); break; }
case 17: { make_jump17(); break; }
case 18: { make_jump18(); break; }
case 19: { make_jump19(); break; }
default: break;
}
}
struct Number {
uint64_t x;
uint64_t L;
std::vector<int> jumps;
Number(uint64_t x_) {
x = x_;
L = MSBL(x_);
std::vector<int> ones;
for (uint64_t b = 4, i = 2; b <= L; b <<= 1, ++i) {
if (x & b) ones.push_back(i);
}
int i = 1;
for (auto o : ones) {
jumps.push_back(o - i);
i = o;
}
}
};
#define PREV3(OP1_, OP2_, OP3_) (OP[i - 2] == OP1_ && OP[i - 1] == OP2_ && OP[i] == OP3_)
#define PREV5(OP1_, OP2_, OP3_, OP4_, OP5_) (OP[i - 4] == OP1_ && OP[i - 3] == OP2_ && PREV3(OP3_, OP4_, OP5_))
#define POP(cnt_) int cnt__ = cnt_; do { OP_new.pop_back(); } while (cnt__--)
bool fix() {
bool fixed = false;
std::vector<std::string> OP_new = {OP[0], OP[1]};
auto sz = OP.size();
for (std::size_t i = 2; i < sz; ++i) {
OP_new.push_back(OP[i]);
// SWAP OVER SWAP => DUP OVER
if (PREV3("SWAP", "OVER", "SWAP")) {
POP(3);
OP_new.push_back("DUP");
OP_new.push_back("OVER");
fixed = true;
}
// DUP SWAP OVER => DUP DUP
if (PREV3("DUP", "SWAP", "OVER")) {
POP(2);
OP_new.push_back("DUP");
fixed = true;
}
// OVER OVER DUP * * => DUP * OVER *
if (i >= 4 && PREV5("OVER", "OVER", "DUP", "*", "*")) {
POP(5);
OP_new.push_back("DUP");
OP_new.push_back("*");
OP_new.push_back("OVER");
OP_new.push_back("*");
}
}
OP = OP_new;
return fixed;
}
// Stack assumption when building normally:
// - [2, L], where L is current 1 << b
int main() {
int t;
std::cin >> t;
for (int i = 0; i < t; ++i) {
si = 0;
S[0] = 1;
OP.clear();
uint64_t x;
std::cin >> x;
assert(x >= 4);
if (VERBOSE) std::cout << "Solving: " << x << '\n';
Number n(x);
if (VERBOSE) {
for (auto i = 1, bi = 1; i < 20; ++i, bi <<= 1) {
std::cout << ((x & bi) ? 1 : 0);
}
std::cout << '\n';
std::cout << "JUMPS:";
for (const auto jmp : n.jumps) std::cout << " " << jmp;
std::cout << '\n';
}
if (x & 1) {
DUP; // [1, 1]
}
DUP; // [1, 1, 1] or [1, 1]
PLUS; // [1, 2] or [2]
DUP; // [1, 2, 2] or [2, 2]
print_stack();
for (std::size_t j = 0; j < n.jumps.size(); ++j) {
auto jmp = n.jumps[j];
// Keep current one:
if (j > 0 || (x & 2)) {
SWAP; // [.., L, 2]
OVER; // [.., L, 2, L]
}
const auto retain = j != n.jumps.size() - 1;
if (jmp == 1) {
if (retain) {
OVER; // [.., L, 2, L, 2];
}
MULTIPLY; // [.., L, 2?, L * 2]
} else {
jump(jmp, retain); // [L, 2?, L, jmp]
MULTIPLY; // [L, 2?, L * jmp]
}
print_stack();
}
while (si > 0) {
PLUS;
print_stack();
}
assert(si == 0);
assert(S[0] == x);
while (fix()) { };
std::cout << OP.size() << '\n';
for (const auto& op : OP) {
std::cout << op << ' ';
}
std::cout << '\n';
}
}
