Problem: Example

Input

2
5 6
1000000000 2


Output

4
5 6
0 6
0 0
5 0
3
1000000000 0
0 2
999999999 0

Solution (in CPP):

Solution:
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "vector"
#include "string"

using namespace std;

const long long int MOD = 1000000007;

int gcd(int a, int b) {
	while (b) {
		a %= b;
		a ^= b ^= a ^= b;
	}
	return a;
}

long long int extended_gcd(long long int a, long long int b, long long int c, long long int d, long long int m) {
	long long int ret = 0;
	if (c == 1)return d;
	ret = extended_gcd(c, d, a%c, (b + (MOD *MOD / m)*m - (a / c)*d) % m, m);
	return ret;
}

long long int extended_gcd(long long int a, long long int b) {
	int g = gcd(a, b);
	a /= g;
	b /= g;
	long long int box = a % b;
	long long int bag = b - (a % b);
	long long int bbox = 1;
	long long int bbag = b - 1;
	return extended_gcd(box, bbox, bag, bbag, b)*g;
}

long long int N, M, K, H, W, L, R;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> N;
	vector<vector<pair<int, int>>>ans(N);
	for (int i = 0; i < N; i++) {
		cin >> W >> H;
		vector<pair<int, int>>add;
		int g = gcd(W, H);
		bool ch = false;
		if (W > H) {
			swap(H, W);
			ch = true;
		}
		if (H == W) {
			add.push_back({ 0,0 });
			add.push_back({ W , H - 1 });
			add.push_back({ 1,1 });
			add.push_back({ W - 1,H });
		}
		else if (g == 1) {
			long long int x = extended_gcd(H, W);
			long long int y = (x*H + 1) / W;
			add.push_back({ 0,0 });
			add.push_back({ W,H });
			add.push_back({ x,y });
		}
		else {
			long long int box = H * W * 2;
			box -= W * (H - 1);
			box -= H * (W - 1);
			box -= W - W / g;
			box -= H - H / g;
			long long int bag = H * W;
			long long int x = extended_gcd(H / g, W / g);
			long long int y = (x*(H / g) + 1) / (W / g);
			bag -= y * x;
			bag -= (H - y)*x * 2;
			bag -= (H - y)*(W - x);
			if (box <= 50000) {
				add.push_back({ 0,0 });
				add.push_back({ W ,H - 1 });
				add.push_back({ W / g,H / g });
				add.push_back({ W - 1,H });
			}
			else {
				add.push_back({ 0,0 });
				add.push_back({ W,H });
				add.push_back({ x,y });
			}
		}
		if (ch) {
			for (auto &j : add) {
				swap(j.first, j.second);
			}
		}
		ans[i] = add;
	}
	for (auto i : ans) {
		cout << i.size() << endl;
		for (auto j : i) {
			cout << j.first << " " << j.second << endl;
		}
	}
	return 0;
}