#include <iostream>
#include <queue>
#include <string>
using namespace std;
typedef unsigned int uint;

//======================================================================
const uint maxn = 10000;

//======================================================================
class State;
static State* _source = NULL;
static State* _target = NULL;
static char* _toDigit = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";

class State {
	State* _parent; 
	uint _level;
	uint _digit;
public:
	void set(State* parent, uint level, uint digit) {
		_parent = parent;
		_level = level;
		_digit = digit;
	}
	void unset() { set(0, 0, 0); }
	bool isSet() { return _parent != 0; }
	State* getParent() const { return _parent; }
	uint getLevel() const { return _level; } 
	string getDigit() const { return string("") + _toDigit[_digit]; }
	uint getSum() const { return (this - _source) / maxn; }
	uint getResidue() const { return (this - _source) % maxn; }
	friend ostream& operator<<(ostream& strm, const State& state);
};

//======================================================================
ostream& operator<<(ostream& strm, const State& state) {
	return strm
		<< "(" << state.getSum()
		<< "," << state.getResidue()
		<< "," << state.getLevel()
		<< ")";
}

//======================================================================
static State _table[maxn+1][maxn];

//======================================================================
// Return string for smallest multiple of n with digit sum n
string f(uint n, uint base = 10) {

	// Bounds checking
	if (n > maxn || base < 2 || base > 36)
		return "Unknown";

	// Return solution for n = 0
	if (n <= 0) return "0";

	// Set source and target states
	_source = &_table[0][0];
	_target = &_table[n][0];

	// Clear all states
	for (uint s = 0; s <= n; s++)
		for (uint r = 0; r < n; r++)
			_table[s][r].unset();

	// Set source state
	_source->set(_source, 0, 0);

	// Add source state to queue
	queue<State*> stateQueue;
	stateQueue.push(_source);

	// Loop through queue
	for (;;) {

		// If queue empty, we failed
		if (stateQueue.empty()) return "None";

		// Pop parent
		State* parent = stateQueue.front();
		stateQueue.pop();

		// For each digit
		for (
			uint digit = 0,
			level = parent->getLevel()+1,
			sum = parent->getSum(), 
			residue = (base*parent->getResidue())%n;

			digit < base && sum <= n;

			digit++,
			sum++,
			residue = (residue+1)%n
		) {
			// Find child state
			State* child = &_table[sum][residue];

			// If child already set, skip it
			if (child->isSet()) continue;

			// Set the child
			child->set(parent, level, digit);

			// If target is set, go create number
			if (_target->isSet()) goto buildAnswer;

			// Add child to queue
			stateQueue.push(child);
		}
	}

	// Build answer
	buildAnswer:
	string answer = "";
	for (State* s = _target; s != _source; s = s->getParent())
		answer = s->getDigit() + answer;

	// Return answer
	return answer;
}

// Generate b-file for A002998
int main() {
	for (uint n = 0; n <= maxn; n++)
		cout << n << " " << f(n) << endl;
	return 0;
}