#include <stdio.h> 
long long exgcd(long long x, long long y, long long &a, long long &b) {
    // ax + by = gcd(x,y)
    int flag = 0;
    long long t, la = 1, lb = 0, ra = 0, rb = 1;
    while(x%y) {
        if(flag == 0)
            la -= x/y*ra, lb -= x/y*rb;
        else
            ra -= x/y*la, rb -= x/y*lb;
        t = x, x = y, y = t%y;
        flag = 1 - flag;
    }
    if(flag == 0)
        a = ra, b = rb;
    else
        a = la, b = lb;
    return y;
}
long long countSolution(long long n1, long long n2, long long n) {
	long long a, b, g;
    g = exgcd(n1, n2, a, b); // a*n1 + b*n2 = gcd(n1,2)
    if(n%g) return 0;
	long long k = n/g, k1, k2;
    a *= k, b *= k;// a*n1 + b*n2 = n
    // (a+F)*n1 + (b+G)*n2 = n =>  Fn1 + Gn2 = 0,
    //F = lcm(n1, n2)/n1 * i, G = lcm(n1, n2)/n2 * i
    k1 = n1*n2/g/n1, k2 = n1*n2/g/n2;
    if(a < 0) { // adjust a >= 0
        k = -(a/k1) + (a%k1 != 0);
        a += k*k1, b -= k*k2;
    }
    if(b < 0) { // adjust b >= 0
        k = -(b/k2) + (b%k2 != 0);
        a -= k*k1, b += k*k2;
    }
    if(a < 0 || b < 0) return 0;
    long long x1, x2, y1, y2;
    // minimize a, maximize b
    k = a/k1;
    a -= k*k1;
    b += k*k2;
    x1 = a, y1 = b;
    // maximize a, minimize b
    k = b/k2;
    a += k*k1;
    b -= k*k2;
    x2 = a, y2 = b;
    return (x2 - x1) / k1 + 1;
}
int main() {
	int testcase, cases = 0;
	long long A, B, C, P, ret, ta, tb;
	scanf("%d", &testcase);
	while (testcase--) {
		scanf("%lld %lld %lld %lld", &A, &B, &C, &P);
		long long g = exgcd(exgcd(A, B, ta, tb), C, ta, tb);
		P /= g, A /= g, B /= g, C /= g;
		ret = 0;
		for (long long i = 0; P - C * i >= 0; i++)
			ret += countSolution(A, B, P - C * i);
		printf("Case %d: %lld\n", ++cases, ret);
	}
	return 0;
}
/*
1
202 203 200 606
*/

#include <stdio.h> 
#include <algorithm>
#include <queue>
#include <assert.h>
using namespace std;
const int dx[] = {-1, 0, 1, 0}; // N E S W 
const int dy[] = {0, 1, 0, -1};
int used[100][100][4][1<<8] = {}, testcase = 0;
int dist[100][100][4][1<<8] = {};
int main() {
	int N, M, K, x, y;
	char g[128][128];
	while (scanf("%d %d", &N, &M) == 2 && N+M) {
		int treasure[128][128] = {}, dirg[128][128] = {};
		for (int i = 0; i < N; i++) {
			scanf("%s", g[i]);
			for (int j = 0; j < M; j++) {
				if (g[i][j] == 'N')
					dirg[i][j] = 0;			
				if (g[i][j] == 'E')
					dirg[i][j] = 1;	
				if (g[i][j] == 'S')
					dirg[i][j] = 2;	
				if (g[i][j] == 'W')
					dirg[i][j] = 3;
			}
		}
		scanf("%d", &K);
		for (int i = 0; i < K; i++) {
			scanf("%d %d", &x, &y);
			x--, y--;
			assert(treasure[x][y] == 0);
			treasure[x][y] = i + 1;
		}
		queue<int> X, Y, D, T;
		int x = 0, y = 0, d = 0, t = 0;
		int tx, ty, td, tt;
		if (treasure[x][y])
			t |= 1<<(treasure[x][y] - 1);
		X.push(x), Y.push(y), D.push(d), T.push(t);
		testcase++;
		used[x][y][d][t] = testcase;
		dist[x][y][d][t] = 0;
		while (!X.empty()) {
			x = X.front(), X.pop();
			y = Y.front(), Y.pop();
			d = D.front(), D.pop();
			t = T.front(), T.pop();	
					
			tx = x, ty = y, td = (d + 1)%4, tt = t;
			if (used[tx][ty][td][tt] != testcase) {
				used[tx][ty][td][tt] = testcase;
				dist[tx][ty][td][tt] = dist[x][y][d][t] + 1;
				X.push(tx), Y.push(ty), D.push(td), T.push(tt);
				if (tx == N - 1 && ty == M - 1 && tt == (1<<K) - 1)
					break;
			}
			
			int dir = (dirg[x][y] + d)%4;
			tx = x + dx[dir], ty = y + dy[dir], td = (d + 1)%4, tt = t;
			if (tx < 0 || ty < 0 || tx >= N || ty >= M)
				continue;
			if (treasure[tx][ty])
				tt |= 1<<(treasure[tx][ty] - 1);
			if (used[tx][ty][td][tt] != testcase) {
				used[tx][ty][td][tt] = testcase;
				dist[tx][ty][td][tt] = dist[x][y][d][t] + 1;
				X.push(tx), Y.push(ty), D.push(td), T.push(tt);
				if (tx == N - 1 && ty == M - 1 && tt == (1<<K) - 1)
					break;
			}
		}
		int ret = 0x3f3f3f3f;
		for (int i = 0; i < 4; i++) {
			if (used[N-1][M-1][i][(1<<K)-1] == testcase)
				ret = min(ret, dist[N-1][M-1][i][(1<<K)-1]);
		}
		printf("%d\n", ret);
	}
	return 0;
}
/*
2 2
EE
NN
1
1 2
1 1
E
1
1 1
1 2
NE
1
1 2
0 0
*/

#include <stdio.h>
#include <map>
#include <vector>
#include <iostream>
#include <fstream>
#include <assert.h>
#include <sstream>
#include <math.h>
#include <ctype.h>
using namespace std;
#define DEBUG
class Model {
	public:
	map<string, int> Count;
	map<pair<string, string>, int> Count2;
	map<int, int> Ni;
	map<int, int> Ni2;
	int totalCountWord, totalCount2Word;
	static const int K;
	static const int V;
	string str2lower(string s) {
		for (int i = 0; i < s.length(); i++)
			s[i] = tolower(s[i]);
		return s;
	}
	void prepare() {
		totalCountWord = totalCount2Word = 0;
		for (map<string, int>::iterator it = Count.begin();
			it != Count.end(); it++) {
			Ni[it->second]++;
			totalCountWord += it->second;
//#ifdef DEBUG
//			if (it->second > 1000)
//			printf("Count(%s) = %d\n", it->first.c_str(), it->second);
//#endif
		}	
		for (map<pair<string, string>, int>::iterator it = Count2.begin();
			it != Count2.end(); it++) {
			Ni2[it->second]++;
			totalCount2Word += it->second;
		}		
		int smooth = 0x3f3f3f3f;
		for (map<int, int>::iterator it = Ni.begin();
			it != Ni.end(); it++) {
//			smooth = min(smooth, it->second);
//			it->second = smooth;
//#ifdef DEBUG
//			printf("N(%d) = %d\n", it->first, it->second);
//			getchar();
//#endif
		}
	}
	double getN(int i) { // N_{Count(w)}
		if (i == 0)	return 80000;
		map<int, int>::iterator it = Ni.lower_bound(i), jt;
		if (it == Ni.begin())	return it == Ni.end() ? 1 : it->second;
		jt = it, jt--;
		double sx = jt->first, sy = jt->second, ex = it->first, ey = it->second;
		return sy + (ey - sy) / (ex - sx) * (i - sx);
	}
	double getN2(int i) { // N_{Count(w_{i}, w_{i+1})}
		if (i == 0)	return 80000.0 * 80000.0;
		map<int, int>::iterator it = Ni2.lower_bound(i), jt;
		if (it == Ni2.begin())	return it == Ni2.end() ? 1 : it->second;
		jt = it, jt--;
		double sx = jt->first, sy = jt->second, ex = it->first, ey = it->second;
		return sy + (ey - sy) / (ex - sx) * (i - sx);
	}
	double getCountStar(const string &w) { // Count^{*}(w_{i})
		int n = Count[w];
		if (n < K) {
			return (double) (n + 1) * (getN(n + 1) / getN(n));
		} else {
			return n;
		}
	}
	double getCountStar2(const string &w1, const string &w2) { // Count^{*}(w_{i}, w_{i+1})
		int n = Count2[make_pair(w1, w2)];
		if (n < K) {
			return (double) (n + 1) * (getN2(n + 1) / getN2(n));
		} else {
			return n;
		}
	}
	double getPofW1(const string &w) { // P(w_{i}) = \frac{Count(w_{i})}{\sum_{j} Count(w_{j})}
		map<string, int>::iterator it = Count.find(w);
		if (it == Count.end() || it->second == 0) { // Count(w_{i}) = 0
			double Nu0 = V - Count.size();
			return (double) getN(1) / Nu0 / totalCountWord; // \frac{N_{1}}{N}
		} else if (it->second < K) { // 0 < Count(w_{i}) < K
			return (double) getCountStar(w) / totalCountWord; // \frac{Count^{*}(w_{i})}{N}
		} else { // Count(w_{i}) \geq K
			return (double) it->second / totalCountWord; // \frac{Count(w_{i})}{N}
		}
	}
	double getPofW2(const string &w1, const string &w2) { // P(w_{i}, w_{i+1})
		map< pair<string, string>, int>::iterator it = Count2.find(make_pair(w1, w2));
		if (it == Count2.end() || it->second == 0) {
			double Nb0 = (double) V * V - Count2.size();
			return (double) getN2(1) / Nb0 / totalCount2Word;
		} else if (it->second < K) { // Count(w_{i}, w_{i+1}) < K
			return (double) getCountStar2(w1, w2) / totalCount2Word; // \frac{Count^{*}(w_{i}, w_{i+1})}{N}
		} else { // Count(w_{i}, w_{i+1}) \geq K
			return (double) it->second / totalCount2Word; // \frac{Count(w_{i}, w_{i+1})}{N}
		}
	}
	void parseStmt(vector<string> &stmt) {
		for (int i = 0; i < stmt.size(); i++) {
			stmt[i] = str2lower(stmt[i]);
			Count[stmt[i]]++;
			if (i)
				Count2[make_pair(stmt[i-1], stmt[i])]++;
		}
	}
	double getPs(string in) {
		stringstream sin(in);
		vector<string> stmt;
		string token;
		while (sin >> token)
			stmt.push_back(str2lower(token));
		// P(s) = P(w_{0}) \times P(w_{1}|w_{0}) \times ... \times P(w_{n-1}|w_{n-2})
		double p = 1;
		if (stmt.size() > 0)
			p = getPofW1(stmt[0]);
		for (int i = 1; i < stmt.size(); i++ ) {
			p *= getPofW2(stmt[i-1], stmt[i]) / getPofW1(stmt[i-1]);
//			printf("%lf\n", getPofW2(stmt[i-1], stmt[i]) / getPofW1(stmt[i-1]));
//			cout << stmt[i-1] << " "  << stmt[i]  << endl; 
//			printf("%lf\n", getPofW2(stmt[i-1], stmt[i]));
		}
		return p;
	}
} tool;
const int Model::K = 10, Model::V = 80000;
int main() {
	ifstream fin("dataset.txt");
//	freopen("tmp.txt", "w+t", stdout); 
	string token, line;
	vector<string> stmt;
	puts("processing dataset.txt ...");
	while (getline(fin, line)) {
		stringstream sin(line);
		stmt.clear();
		while (sin >> token) {
			stmt.push_back(token);
		}
		tool.parseStmt(stmt);
	}
	puts("read file end. Start prepare language model ...");
	tool.prepare();
	puts("input a sentence in a line :");
	while (getline(cin, line)) {
		printf("P*('%s') : %.10e\n", line.c_str(), tool.getPs(line));
	}
	return 0;
}
/*
causes AIDS and is associated with AIDS cases primarily in West Africa
AIDS cases primarily in West Africa
AIDS cases primarily at West Africa
AIDS cases primarily AIDS West Africa
morris
IL-2 is a gene .
IL-2 is an gene .
*/

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
#define MAXN 8192
#define MAXD 8
#define INF 0x3f3f3f3f
class kdTree {
	public:	
	struct PointD {
		int d[MAXD];
		int label;
	};
	struct Node {
    	Node *lson, *rson;
    	int label;
	};
	struct cmp {
		bool operator()(const PointD* x, const PointD* y) const {
    		return x->d[sortDidx] < y->d[sortDidx];
		}
	};
	struct pQcmp {
	    bool operator() (pair<int, int> &a, pair<int, int> &b) const {
	    	if (a.first != b.first)	return a.first < b.first;
	    	return a.second < b.second;
	    }
	};
	static int sortDidx;
	priority_queue<pair<int, int>, vector< pair<int, int> >, pQcmp> pQ; // <dist, label>
	Node buf[MAXN], *root;
	PointD pt[MAXN], *A[MAXN];
	int bufsize, K;
	int Q[MAXD], max_dist, qM;
	void prepare(int n) {
        bufsize = 0;
        for (int i = 0; i < n; i++)
        	A[i] = &pt[i];
        root = build(0, 0, n - 1);
	}
	Node* build(int k, int l, int r) {
	    if(l > r)	return NULL;
	    int m = (l + r)/2;
	    Node *ret = &buf[bufsize++];
	    sortDidx = k;
	    nth_element(A + l, A + m, A + r + 1, cmp());
	    ret->label = A[m]->label, ret->lson = ret->rson = NULL;
	    if(l != r) {
	        ret->lson = build((k+1)%K, l, m-1);
	        ret->rson = build((k+1)%K, m+1, r);
	    }
	    return ret;
	}
	int dist(int idx) {
	    int ret = 0;
	    for(int i = 0; i < K; i++)
	        ret += (pt[idx].d[i] - Q[i]) * (pt[idx].d[i] - Q[i]);
	    return ret;
	}
	int h_func(int h[]) {
	    int ret = 0;
	    for(int i = 0; i < K; i++)	ret += h[i];
	    return ret;
	}
	void findNearest(Node *u, int k, int h[]) {
	    if(u == NULL || h_func(h) >= max_dist)
	        return;
	    int d = dist(u->label);
	    if (d < max_dist) {
	        pQ.push(make_pair(d, u->label));
	        if (pQ.size() == qM + 1) {
	            max_dist = pQ.top().first, pQ.pop();
	        }
	    }
	    int old_hk = h[k];
	    if (Q[k] <= pt[u->label].d[k]) {
	        if (u->lson != NULL)
	            findNearest(u->lson, (k+1)%K, h);
	        if (u->rson != NULL) {
	            h[k] = (pt[u->label].d[k] - Q[k]) * (pt[u->label].d[k] - Q[k]);
	            findNearest(u->rson, (k+1)%K, h);
	            h[k] = old_hk;
	        }
	    } else {
	        if (u->lson != NULL) {
	            h[k] = (pt[u->label].d[k] - Q[k]) * (pt[u->label].d[k] - Q[k]);
	            findNearest(u->lson, (k+1)%K, h);
	            h[k] = old_hk;
	        }
	        if(u->rson != NULL)
	            findNearest(u->rson, (k+1)%K, h);
	    }
	}
	void query(int p[], int M) {
		for (int i = 0; i < K; i++)
			Q[i] = p[i];
	    max_dist = INF, qM = M;
	    int h[MAXD] = {};
		findNearest(root, 0, h);
	    printf("%d", M);
	    vector<int> ret;
	    while (!pQ.empty())
	        ret.push_back(pQ.top().second), pQ.pop();
	    for (int i = ret.size() - 1; i >= 0; i--)
	    	printf(" %d", ret[i] + 1);
	    puts("");
	}
};	
int kdTree::sortDidx;
kdTree tree;
int main() {
//	freopen("in.txt", "r+t", stdin);
//	freopen("out.txt", "w+t", stdout); 
	int n, m, q, p[MAXD], x;
	int cases = 0;
    while (scanf("%d %d", &n, &m) == 2) {
    	tree.K = m;
    	for (int i = 0; i < n; i++) {
    		for (int j = 0; j < m; j++)
    			scanf("%d", &tree.pt[i].d[j]);
    		tree.pt[i].label = i;
    	}
    	tree.prepare(n);
        scanf("%d", &q);
        while (q--) {
        	for (int i = 0; i < m; i++)
        		scanf("%d", &p[i]);
        	scanf("%d", &x);
        	printf("Case %d: ", ++cases);
        	tree.query(p, x);
        }
    }
    return 0;
}
/*
2 2
1 1
3 3
1
2 2
1
3 2
1 1
1 3
3 4
2
2 3
2
2 3
1
*/ 

#include <stdio.h> 
#include <algorithm>
#include <string.h>
using namespace std;
#define MAXN 1024
long long dp[MAXN][MAXN], X[MAXN], W[MAXN];
long long sumW[MAXN] = {}, sumXW[MAXN] = {};
struct SlopeDP {
	int front, rear;
	long long X[MAXN], Y[MAXN];
	void init() {front = 0, rear = -1;}
	long long cross(long long x1, long long y1, long long x2, long long y2) {
		return x1 * y2 - y1 * x2;
	}
	int add(long long x, long long y) {
		while (front < rear && cross(X[rear]-X[rear-1], Y[rear]-Y[rear-1], x-X[rear-1], y-Y[rear-1]) < 0)
			rear--;
		rear++;
		X[rear] = x, Y[rear] = y;
	}
	long long get(long long m) {
		while (front < rear && Y[front+1]-Y[front] < (X[front+1]-X[front]) * m)
			front++;
		return Y[front] - m * X[front];
	}
} dpTool;
int main() {
	int N, M;
	while (scanf("%d %d", &N, &M) == 2) {
		for (int i = 1; i <= N; i++)
			scanf("%lld %lld", &X[i], &W[i]);
		for (int i = 1; i <= N; i++) {
			sumW[i] = sumW[i-1] + W[i];
			sumXW[i] = sumXW[i-1] + X[i] * W[i];
		}
		for (int i = 0; i <= N; i++)
			for (int j = 0; j <= M; j++) 
				dp[i][j] = 1LL<<60;
		dp[0][0] = 0;
//		for (int i = 1; i <= N; i++) {
//			for (int j = 1; j <= M; j++) {
//				for (int k = 0; k < i; k++)
//					dp[i][j] = min(dp[i][j], dp[k][j-1] + X[i] * (sumW[i] - sumW[k]) - (sumXW[i] - sumXW[k]));
//			}
//		}
		for (int i = 1; i <= M; i++) {
			dpTool.init();
			for (int j = i; j <= N; j++) {
				dpTool.add(sumW[j-1], dp[j-1][i-1] + sumXW[j-1]);
				long long val = dpTool.get(X[j]);
				dp[j][i] = val - (sumXW[j] - sumW[j] * X[j]);
			}
		}
		printf("%lld\n", dp[N][M]);
	}
	return 0;
}
/*
dp[i][j] = dp[k][j-1] + X[i] * (sumW[i] - sumW[k]) - (sumXW[i] - sumXW[k])
dp[k][j-1] + sumXW[k] = X[i] * sumW[k] + dp[i][j] + sumXW[i] - sumW[i] * X[i]
^^^^^^^^^^^^^^^^^^^^^   ^^^^   ^^^^^^^   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
y = a x + b, a : monotone increasing, maintain upper convex
*/
/*
3 1
20 1
30 1
40 1
3 1
11 3
12 2
13 1
6 2
10 15
12 17
16 18
18 13
30 10
32 1
6 3
10 15
12 17
16 18
18 13
30 10
32 1
*/

#include <stdio.h> 
#include <vector>
#include <string.h>
#include <algorithm>
#include <map>
using namespace std;
int dp[10005][64][3] = {};
const int mod = 1000000;
int main() {
	freopen("in.txt", "r+t", stdin);
	freopen("out.txt", "w+t", stdout);
	int testcase, n, m, x, y;
	int cases = 0;
	scanf("%d", &testcase);
	while (testcase--) {
		scanf("%d %d", &n, &m);
		vector< pair<int, int> > D;
		map<int, int> R;
		for (int i = 0; i < n; i++) {
			scanf("%d %d", &x, &y);
			R[y] = 0;
			D.push_back(make_pair(x, y));
		}
		sort(D.begin(), D.end());
		int v = 0;
		for (map<int, int>::iterator it = R.begin();
			it != R.end(); it++)
			it->second = v++;
		for (int i = 0; i < n; i++)
			D[i].second = R[D[i].second];
		memset(dp, 0, sizeof(dp));
		int used[10005] = {};
		for (int i = 0; i < n; i++) {
			if (used[D[i].second] == 0) {
				dp[i][0][0] = 1; // =
				dp[i][0][1] = 1; // <
				dp[i][0][2] = 1; // > next time
				used[D[i].second] = 1;
			}
		}
		int ret = 0;
		if (m == 0)
			ret++;
		for (int i = 0; i < n; i++) {
			ret = (ret + dp[i][m][0])%mod;
			memset(used, 0, sizeof(used));
//			for (int k = 0; k <= m; k++) 
//					printf("[%d %d] %d %d %d\n", i, k, dp[i][k][0], dp[i][k][1], dp[i][k][2]);
			for (int j = i+1; j < n; j++) {					
				if (used[D[j].second])	continue;
				used[D[j].second] = 1;
				for (int k = 0; k <= m; k++) {
					if (D[j].second > D[i].second) { // larger
						dp[j][k][0] = (dp[j][k][0] + dp[i][k][2])%mod;
						dp[j][k+1][1] = (dp[j][k+1][1] + dp[i][k][2])%mod;
						dp[j][k][2] = (dp[j][k][2] + dp[i][k][2])%mod;
					} else if (D[j].second == D[i].second) {
//						dp[j][k][0] = (dp[j][k][0] + dp[i][k][0])%mod;
//						dp[j][k][1] = (dp[j][k][1] + dp[i][k][0])%mod;
//						dp[j][k][2] = (dp[j][k][2] + dp[i][k][0])%mod;
					} else {
						dp[j][k][0] = (dp[j][k][0] + dp[i][k][1])%mod;
						dp[j][k][1] = (dp[j][k][1] + dp[i][k][1])%mod;
						dp[j][k+1][2] = (dp[j][k+1][2] + dp[i][k][1])%mod;
					}
				}
			}
		}
		printf("Case %d: %d\n", ++cases, ret);
	}
	return 0;
}

#include <stdio.h>
#include <math.h>
#include <vector>
#include <queue>
#include <iostream>
#include <algorithm>
using namespace std;
class Frac {
	public:
	int x, y;
	Frac(int a = 0, int b = 0):
		x(a), y(b) {}
	double toDouble() const {
		return (double) x/y;
	}
	bool operator<(const Frac &a) const {
		return toDouble() < a.toDouble();
	}
} D[1048576];
double DD[1048576];
double cmpv;
bool cmp(Frac a, Frac b) {
	return fabs(a.toDouble() - cmpv) < fabs(b.toDouble() - cmpv);
}
int f(double v) {
	if (v >= 1000)	return 4;
	if (v >= 100)	return 3;
	if (v >= 10)	return 2;
	return 1;
}
int main() {
//	freopen("in.txt", "r+t", stdin);
//	freopen("out.txt", "w+t", stdout); 
	int n = 0;
	for (int y = 1; y <= 1000; y++) {
		for (int x = 1; x <= 1000; x++) {
			if (__gcd(x, y) == 1)
				D[n++] = Frac(x, y);
		}
	}
	sort(D, D + n);
	for (int i = 0; i < n; i++)
		DD[i] = D[i].toDouble();
	char s[32];
	double v;
	while (scanf("%s", s) == 1) {
		printf("Input : %s\n", s);
		sscanf(s, "%lf", &v);
		int pos = lower_bound(DD, DD + n, v) - DD;
		vector<Frac> A;
		for (int i = max(0, pos - 6); i < min(n, pos + 6); i++)
			A.push_back(D[i]);
		cmpv = v;
		sort(A.begin(), A.end(), cmp);
		for (int i = 0, j = 1; i < 3 && i < A.size(); i++, j++)
			printf("    %d : %*.*lf = %4d / %d\n", j, f(A[i].toDouble()), 10 - f(A[i].toDouble()), A[i].toDouble(), A[i].x, A[i].y);
	}
	return 0;
}