wowoto9772

#include <cstdio>
#include <limits.h>
#include <functional>

#include <vector>
#include <queue>

using namespace std;

#define cst first

wowoto9772

#include <cstdio>
#include <queue>

using namespace std;
using ll = long long;

int main() {

	int t;
	scanf("%d", &t);

wowoto9772

#include <cstdio>
#include <queue>

using namespace std;

class ele {
public:
	int r, c, cst;
	ele() {}
	ele(int r_, int c_, int cst_) { r = r_, c = c_, cst = cst_; }

wowoto9772

#include <cstdio>
#include <memory.h>
#include <algorithm>

using namespace std;
using ll = long long;

int e[2000];
int b[2000];
ll dp[2000][2000];

wowoto9772

#include <cstdio>

using namespace std;

int prime_factor[5000001];

int main() {

	for (int i = 2; i <= 5000000; i++)prime_factor[i] = i;
	for (int i = 2; i * i <= 5000000; i++) {

wowoto9772

#include <cstdio>
#include <vector>

using namespace std;

int main() {

	int n;
	while (scanf("%d", &n) == 1 && n) {

wowoto9772

#include <cstdio>
#include <limits.h>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

class ele {
public:

wowoto9772

#include <cstdio>
#include <memory.h>

using namespace std;

const int impossible = 0;
const int imod = 9901;

int dp[201][101];

wowoto9772

#include <cstdio>

using namespace std;

using ll = long long;

ll split_sum(ll a) {

	ll v = a;
	while (a > 0) {

wowoto9772

#include <cstdio>
#include <algorithm>

using namespace std;

char S[100003], B[100003];
int s_pos[100003], b_pos[100003];

using ll = long long;