1. 1
2. 2
3. 3
4. 4
5. 5
6. 6
7. 7
8. 8
9. 9
10. 10
11. 11
12. 12
13. 13
14. 14
15. 15
16. 16
17. 17
18. 18
19. 19
20. 20
21. 21
22. 22
23. 23
24. 24
25. 25
26. 26
27. 27
28. 28
29. 29
30. 30
31. 31
32. 32
33. 33
34. 34
35. 35
36. 36
37. 37
38. 38
39. 39
40. 40
41. 41
42. 42
43. 43
44. 44
45. 45
46. 46
47. 47
48. 48
49. 49
50. 50
51. 51
52. 52
53. 53
54. 54
55. 55
56. 56
57. 57
58. 58
59. 59
60. 60
61. 61
62. 62
63. 63
64. 64
65. 65
66. 66
67. 67
68. 68
69. 69
70. 70
71. 71
72. 72
73. 73

#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
using ll = long long;
using ii = pair<int, int>;
constexpr int MX = 5;

char A[MX*MX];
bitset<MX*MX> vis;
map<vector<int>, int> dp;

int f(vector<int> & v) {
	for (int i = 1; i < MX; ++i) if (v[i-1] < v[i]) return 0;
	for (int i = 0; i < MX; ++i) if (v[i] > MX) return 0;
	
	int sum = 0;
	for (int i = 0; i < MX; ++i) sum += v[i];
	if (sum == MX*MX) return 1;
	
	if (dp.find(v) != dp.end()) return dp[v];

	int ret = 0;
	for (int i = 0; i < MX; ++i)
		if (A[i*MX+v[i]] == 'A'+sum || !A[i*MX+v[i]])
			++v[i], ret += f(v), --v[i];
	return dp[v] = ret;
}

string getk(int k) {
	string ret(MX*MX, '0');

	vis.reset();
	memset(A, 0, sizeof A);
	for (int i = 0; i < MX*MX; ++i) {
		for (int j = 0; j < MX*MX; ++j) {
			if (vis[j]) continue;
			vis[j] = 1;
			
			A[i] = 'A'+j;
			dp.clear();
			vector<int> v(MX, 0);
			int tmp = f(v);
			
			if (tmp >= k) break;
			k -= tmp;
			vis[j] = 0;
		}
		ret[i] = A[i];
	}
	return ret;
}

int main() {
	if (fopen("in", "r")) freopen("in", "r", stdin), freopen("out", "w", stdout);
	ios_base::sync_with_stdio(0), cin.tie(0);

	char c; cin >> c;
	if (c == 'N') {
		int M; cin >> M;
		cout << getk(M);
	}
	else {
		string S; cin >> S;
		int l = 0, h = 1e9;
		while (l < h) {
			int m = (l+h)/2;
			string tmp = getk(m);
			tmp < S ? l = m+1 : h = m;
		}
		cout << l;
	}
}