#include "currency.h"
#include <bits/stdc++.h>
using namespace std;

#define all(x) (x).begin(), (x).end()
#define ssz(x) (int((x).size()))

auto chmax = [](auto& x, auto y) { if (x < y) x = y; };
auto chmin = [](auto& x, auto y) { if (y < x) x = y; };

using ll = long long;

const int N = 1e3;
const ll L = 1e18;

bool isp[N + 1];
int ans[N];

void solve(int type)
{
assert(type == 2);
	vector<int> p;
	for (int i = 2; i <= N; i++)
		if (!isp[i])
		{
			for (int j = i * 2; j <= N; j += i)
				isp[j] = 1;
			p.push_back(i);
		}
	
	auto mx = [&](int x, int el = 1)
	{
		int c = 1, d = 0;
		while (c * x * el <= N)
			c *= x, d++;
		return make_pair(c, d);
	};
	
	vector<pair<int, ll>> cs;
	
	int ci = 0;
	while (ci < ssz(p))
	{
		int cj = 0, cd = 0;
		ll cv = 1;
		while (cj < ci && p[cj] * p[ci] <= N)
		{
			auto [c, d] = mx(p[cj], p[ci]);
			if (L / cv < c)
				break;
			cv *= c, cj++;
			cd += (d <= 1 ? d : __lg(d - 1) + 1);
			// cerr << cv << " " << c << endl;
		}
		while (ci < ssz(p))
		{
			auto [c, d] = mx(p[ci]);
			if (L / cv < c)
				break;
			cv *= c, ci++;
			cd += (d <= 1 ? d : __lg(d - 1) + 1);
		}
		cs.emplace_back(cd, cv);
	}
	sort(all(cs), greater());
	for (auto [_, x] : cs)
		if (query(x))
		{
			// cerr << x << " start" << endl;
			for (int i = 2; i <= N; i++)
				if (!isp[i] && x % i == 0)
				{
					int l = 0, r = 0; ll y = x;
					for ( ; y % i == 0; r++, y /= i);
					while (l < r)
					{
						int mid = (l + r) >> 1;
						ll z = y;
						for (int j = 0; j < mid; j++)
							z *= i;
						if (query(z))
							r = mid;
						else
							l = mid + 1;
					}
					// cerr << l << " " << r << endl;
					for (int j = 0; j < l; j++)
						y *= i;
					x = y;
				}
			ans[0] = x;
			answer(1, ans);
			break;
		}
}