#include <cstdio>
#include <algorithm>
#include <cmath>
#include <functional>
#include <vector>

typedef unsigned int uint;
typedef long long unsigned int uint64;

inline uint _udiv64(uint64 u, uint v)
{
	uint u0 = u, u1 = u >> 32;
	uint q, r;
	__asm__("divl %[v]" : "=a"(q), "=d"(r) : [v] "r"(v), "a"(u0), "d"(u1));
	return q;
}

constexpr uint Mod = 469762049;

inline constexpr uint norm(const uint x)
{
	return x < Mod ? x : x - Mod;
}

struct Z
{
	uint v;
	Z() { }
	constexpr Z(const uint _v) : v(_v) { }
};

inline constexpr Z operator+(const Z x1, const Z x2) { return norm(x1.v + x2.v); }
inline constexpr Z operator-(const Z x1, const Z x2) { return norm(x1.v + Mod - x2.v); }
inline constexpr Z operator-(const Z x) { return x.v ? Mod - x.v : 0; }
inline constexpr Z operator*(const Z x1, const Z x2) { return static_cast<uint64>(x1.v) * x2.v % Mod; }
inline Z &operator+=(Z &x1, const Z x2) { return x1 = x1 + x2; }
inline Z &operator-=(Z &x1, const Z x2) { return x1 = x1 - x2; }
inline Z &operator*=(Z &x1, const Z x2) { return x1 = x1 * x2; }
inline bool operator==(const Z x1, const Z x2) { return x1.v == x2.v; }
inline bool operator!=(const Z x1, const Z x2) { return x1.v != x2.v; }

struct DS
{
	static uint64 N;
	static int R2;
	
	std::vector<Z> sv;
	std::vector<Z> lv;
	
	DS() : sv(1 + R2, 0), lv(1 + R2, 0) { }
	
	Z &operator[](const uint64 x)
	{
		return x <= R2 ? sv[x] : lv[N / x];
	}
	
	const Z &operator[](const uint64 x) const
	{
		return x <= R2 ? sv[x] : lv[N / x];
	}
	
	void partial_sum()
	{
		for (int i = 2; i <= R2; ++i)
			sv[i] += sv[i - 1];
		lv[R2] += sv[R2];
		for (int i = R2 - 1; i >= 1; --i)
			lv[i] += lv[i + 1];
	}
	
	void adjacent_difference()
	{
		for (int i = 1; i != R2; ++i)
			lv[i] -= lv[i + 1];
		lv[R2] -= sv[R2];
		for (int i = R2; i >= 2; --i)
			sv[i] -= sv[i - 1];
	}
};
uint64 DS::N;
int DS::R2;

inline void add(Z &x, const uint a, const uint b)
{
	x = (x.v + 1ULL * a * b) % Mod;
}
inline void add(Z &x, const Z a, const uint b) { add(x, a.v, b); }
inline void add(Z &x, const Z a, const Z b) { add(x, a.v, b.v); }
inline void sub(Z &x, const Z a, const Z b) { add(x, a.v, Mod - b.v); }

template<typename I>
struct subrange
{
	I i, s;
	
	subrange(I _i, I _s) : i(_i), s(_s) { }
	
	const I &begin() const { return i; }
	const I &end() const { return s; }
	bool empty() const { return i == s; }
	auto size() const { return s - i; }
};

DS operator*(const DS &a, const DS &b)
{
	const uint64 &N = DS::N;
	const int &R2 = DS::R2;
	
	DS res;
	
	auto s1 = [](const DS &ds) -> std::vector<std::pair<int, Z>>
	{
		std::vector<std::pair<int, Z>> vec;
		for (int i = 1; i <= R2; ++i)
			if (ds.sv[i] != ds.sv[i - 1])
				vec.emplace_back(i, ds.sv[i] - ds.sv[i - 1]);
		vec.emplace_back(R2 + 1, 0);
		return vec;
	};
	
	auto s2 = [&res](const int x, const Z y, const std::vector<std::pair<int, Z>> &p, const int l, const int r)
	{
		int i = l;
		for (const int X = R2 / x; i != r && p[i].first <= X; ++i)
			add(res.sv[x * p[i].first], y, p[i].second);
		for (const uint64 Nx = N / x; i != r; ++i)
			add(res.lv[_udiv64(Nx, p[i].first)], y, p[i].second);
	};
	
	auto s3 = [&res](const int x, const Z y, int i, const DS &ds)
	{
		const uint64 Nx = N / x;
		for (int X = R2 / x; i > X; --i)
			add(res.lv[i], y, ds.sv[_udiv64(Nx, i)]);
		for (; i >= 1; --i)
			add(res.lv[i], y, ds.lv[x * i]);
	};
	
	if (&a == &b)
	{
		const auto pa = s1(a);
		// const auto va = std::ranges::subrange(pa.begin(), pa.end() - 1);
		const auto va = subrange(pa.begin(), pa.end() - 1);
		
		for (int l = 0, r = va.size(); const auto &[x, y] : va)
		{
			++l;
			const uint64 Nx = N / x;
			while (r > l && Nx / pa[r - 1].first < r - 1)
				--r;
			if (r < l)
				r = l;
			add(res[1ULL * x * x], y, y);
			s2(x, y * 2, pa, l, r);
			if (r)
				sub(res[1ULL * x * pa[r].first], y, a.sv[pa[r - 1].first] * 2);
		}
		
		res.partial_sum();
		
		for (int l = 0, r = va.size(); const auto &[x, y] : va)
		{
			++l;
			const uint64 Nx = N / x;
			while (r > l && Nx / pa[r - 1].first < r - 1)
				--r;
			if (r < l)
				r = l;
			s3(x, y * 2, _udiv64(Nx, pa[r].first), a);
		}
	}
	else
	{
		const auto pa = s1(a);
		// const auto va = std::ranges::subrange(pa.begin(), pa.end() - 1);
		const auto va = subrange(pa.begin(), pa.end() - 1);
		const auto pb = s1(b);
		// const auto vb = std::ranges::subrange(pb.begin(), pb.end() - 1);
		const auto vb = subrange(pb.begin(), pb.end() - 1);
		
		for (int i = 1; i <= R2; ++i)
			add(res[1ULL * i * i], a.sv[i] - a.sv[i - 1], b.sv[i] - b.sv[i - 1]);
		
		for (int l = 0, r = vb.size(); const auto &[x, y] : va)
		{
			while (pb[l].first <= x)
				++l;
			const uint64 Nx = N / x;
			while (r > l && Nx / pb[r - 1].first < r - 1)
				--r;
			if (r < l)
				r = l;
			s2(x, y, pb, l, r);
			if (r)
				sub(res[1ULL * x * pb[r].first], y, b.sv[pb[r - 1].first]);
		}
		for (int l = 0, r = va.size(); const auto &[x, y] : vb)
		{
			while (pa[l].first <= x)
				++l;
			const uint64 Nx = N / x;
			while (r > l && Nx / pa[r - 1].first < r - 1)
				--r;
			if (r < l)
				r = l;
			s2(x, y, pa, l, r);
			if (r)
				sub(res[1ULL * x * pa[r].first], y, a.sv[pa[r - 1].first]);
		}
		
		res.partial_sum();
		
		for (int l = 0, r = vb.size(); const auto &[x, y] : va)
		{
			while (pb[l].first <= x)
				++l;
			const uint64 Nx = N / x;
			while (r > l && Nx / pb[r - 1].first < r - 1)
				--r;
			if (r < l)
				r = l;
			s3(x, y, _udiv64(Nx, pb[r].first), b);
		}
		
		for (int l = 0, r = va.size(); const auto &[x, y] : vb)
		{
			while (pa[l].first <= x)
				++l;
			const uint64 Nx = N / x;
			while (r > l && Nx / pa[r - 1].first < r - 1)
				--r;
			if (r < l)
				r = l;
			s3(x, y, _udiv64(Nx, pa[r].first), a);
		}
	}
	
	return res;
}

DS mult_sparse(const DS &a, const DS &b)
{
	const uint64 &N = DS::N;
	const int &R2 = DS::R2;
	
	DS res;
	
	auto s1 = [](const DS &ds) -> std::vector<std::pair<int, Z>>
	{
		std::vector<std::pair<int, Z>> vec;
		for (int i = 1; i <= R2; ++i)
			if (ds.sv[i] != ds.sv[i - 1])
				vec.emplace_back(i, ds.sv[i] - ds.sv[i - 1]);
		vec.emplace_back(R2 + 1, 0);
		return vec;
	};
	
	auto s2 = [&res](const int x, const Z y, const std::vector<std::pair<int, Z>> &p, const int r)
	{
		int i = 0;
		for (const int X = R2 / x; i != r && p[i].first <= X; ++i)
			add(res.sv[x * p[i].first], y, p[i].second);
		for (const uint64 Nx = N / x; i != r; ++i)
			add(res.lv[_udiv64(Nx, p[i].first)], y, p[i].second);
	};
	
	auto s3 = [&res](const int x, const Z y, int i, const DS &ds)
	{
		const uint64 Nx = N / x;
		for (int X = R2 / x; i > X; --i)
			add(res.lv[i], y, ds.sv[_udiv64(Nx, i)]);
		for (; i >= 1; --i)
			add(res.lv[i], y, ds.lv[x * i]);
	};

	const auto pa = s1(a);
	// const auto va = std::ranges::subrange(pa.begin(), pa.end() - 1);
	const auto va = subrange(pa.begin(), pa.end() - 1);
	const auto pb = s1(b);
	// const auto vb = std::ranges::subrange(pb.begin(), pb.end() - 1);
	const auto vb = subrange(pb.begin(), pb.end() - 1);
	
	for (int l = 0, r = va.size(); const auto &[x, y] : vb)
	{
		const uint64 Nx = N / x;
		while (r && Nx / pa[r - 1].first < r - 1)
			--r;
		s2(x, y, pa, r);
		if (r)
			sub(res[1ULL * x * pa[r].first], y, a.sv[pa[r - 1].first]);
	}
	for (const auto &[x, y] : va)
	{
		sub(res.lv[_udiv64(R2, x)], y, b.sv[R2]);
	}
	
	res.partial_sum();
	
	for (int l = 0, r = va.size(); const auto &[x, y] : vb)
	{
		const uint64 Nx = N / x;
		while (r && Nx / pa[r - 1].first < r - 1)
			--r;
		s3(x, y, _udiv64(Nx, pa[r].first), a);
	}
	for (const auto &[x, y] : va)
	{
		for (int j = 1; x * j <= R2; ++j)
			add(res.lv[j], y, b.lv[x * j]);
	}
	
	return res;
}

DS calc(const uint64 N, const Z A, const Z B)
{
	DS::N = N;
	const int R2 = std::sqrt(N + 0.5);
	DS::R2 = R2;
	if (N == 0)
		return DS();
	if (N == 1)
	{
		DS ds;
		ds.sv[1] = ds.lv[1] = 1;
		return ds;
	}
	
	Z _Rec[65];
	_Rec[1] = 1;
	for (int i = 2; i <= 64; ++i)
		_Rec[i] = (Mod - Mod / i) * _Rec[Mod % i];
	
	const int R4 = std::sqrt(R2 + 0.5);
	const int R6 = std::cbrt(R2 + 0.5);
	
	std::vector<char> pf(1 + R2);
	std::vector<int> P;
	int L = -1;
	
	for (int p = 2; p <= R2; ++p)
		if (!pf[p])
		{
			if (L == -1 && p > R6)
				L = P.size();
			if (p <= R4)
				for (int j = p * p; j <= R2; j += p)
					pf[j] = 1;
			P.push_back(p);
		}
	if (L == -1)
		L = P.size();
	
	auto attach_powerful = [&](DS &ds, const std::function<Z (uint64, uint, uint)> &f) -> DS & // `ds` is the `DS` of `f` without powerful
	{
		DS powerful;
		auto gen = [&](int i, const uint64 x, const Z y)
		{
			auto gen_rec = [&](const auto &self, int i, const uint64 x, const Z y) -> void
			{
				powerful[x] += y;
				for (; i != P.size() && 1ULL * P[i] * P[i] <= N / x; ++i)
				{
					const uint64 Nx = N / x;
					const int p = P[i];
					const Z fp = f(p, p, 1);
					// assert(fp == ds.sv[p] - ds.sv[p - 1]);
					uint64 pe = 1ULL * p * p;
					Z fpe = 0;
					for (int e = 2; pe <= Nx; pe *= p, ++e)
					{
						fpe = f(pe, p, e) - fpe * fp;
						if (fpe.v)
							self(self, i + 1, x * pe, y * fpe);
					}
				}
			};
			return gen_rec(gen_rec, i, x, y);
		};
		gen(0, 1, 1);
		powerful.partial_sum();
		return ds = mult_sparse(ds, powerful);
	};
	
	auto fix_powerful = [&](DS &ds, const std::function<Z (uint64, uint, uint)> &f, const std::function<Z (uint64, uint, uint)> &now) -> DS &
	{
		DS powerful;
		auto gen = [&](int i, const uint64 x, const Z y)
		{
			auto gen_rec = [&](const auto &self, int i, const uint64 x, const Z y) -> void
			{
				powerful[x] += y;
				for (; i != P.size() && 1ULL * P[i] * P[i] <= N / x; ++i)
				{
					const uint64 Nx = N / x;
					const int p = P[i];
					Z fp[55] = {1, 0};
					Z nowp[55] = {1, now(p, p, 1)};
					// assert(f(p, p, 1) == ds.sv[p] - ds.sv[p - 1]);
					// assert(f(p, p, 1) == nowp[1]);
					uint64 pe = 1ULL * p * p;
					for (int e = 2; pe <= Nx; pe *= p, ++e)
					{
						fp[e] = f(pe, p, e);
						nowp[e] = now(pe, p, e);
						for (int ee = 0; ee < e; ++ee)
							fp[e] -= fp[ee] * nowp[e - ee];
						if (fp[e].v)
							self(self, i + 1, x * pe, y * fp[e]);
					}
				}
			};
			return gen_rec(gen_rec, i, x, y);
		};
		gen(0, 1, 1);
		powerful.partial_sum();
		return ds = mult_sparse(ds, powerful);
	};
	
	auto mult_powerful = [&](const DS &ds, const std::function<Z (uint64, uint, uint)> &f) // `ds` is the `DS` of another function
	{
		DS powerful;
		auto gen = [&](int i, const uint64 x, const Z y)
		{
			auto gen_rec = [&](const auto &self, int i, const uint64 x, const Z y) -> void
			{
				powerful[x] += y;
				for (; i != P.size() && 1ULL * P[i] * P[i] <= N / x; ++i)
				{
					const uint64 Nx = N / x;
					const int p = P[i];
					uint64 pe = 1ULL * p * p;
					for (int e = 2; pe <= Nx; pe *= p, ++e)
					{
						Z fpe = f(pe, p, e);
						if (fpe.v)
							self(self, i + 1, x * pe, y * fpe);
					}
				}
			};
			return gen_rec(gen_rec, i, x, y);
		};
		gen(0, 1, 1);
		powerful.partial_sum();
		return mult_sparse(ds, powerful);
	};
	
	auto attach_small = [&](DS &ds, const std::function<Z (uint)> &f) -> DS & // no small p in `ds`!
	{
		ds.adjacent_difference();
		std::vector<int> pred(1 + R2 + 1);
		pred[1] = 0;
		for (int i = 2; i <= R2 + 1; ++i)
			pred[i] = ds.sv[i - 1].v ? i - 1 : pred[i - 1];
		for (int pid = L - 1; pid >= 0; --pid)
		{
			const int p = P[pid];
			Z y = f(p);
			{
				int j = 1, k = p;
				for (; (j + 1) * p - 1 <= R2; ++j)
					for (; k != (j + 1) * p; ++k)
						if (ds.lv[k].v)
							add(ds.lv[j], ds.lv[k], y);
				for (; k <= R2; ++k)
					if (ds.lv[k].v)
						add(ds.lv[j], ds.lv[k], y);
			}
			{
				int j = pred[R2 + 1];
				uint64 Nx = N / p;
				for (int X = R2 / p; j > X; j = pred[j])
					add(ds.lv[_udiv64(Nx, j)], ds.sv[j], y);
				int k = R2 + 1;
				for (; j; j = pred[j])
				{
					while (pred[k] > j * p)
						k = pred[k];
					// assert(k != j * p);
					pred[j * p] = pred[k], pred[k] = j * p;
					add(ds.sv[j * p], ds.sv[j], y);
				}
			}
		}
		ds.partial_sum();
		return ds;
	};
	
	auto eliminate_small = [&](DS &ds, const std::function<Z (uint)> &f) // no small p in `ds * f`
	{
		ds.adjacent_difference();
		std::vector<int> succ(1 + R2 + 1);
		succ[R2] = R2 + 1;
		for (int i = R2 - 1; i >= 0; --i)
			succ[i] = ds.sv[i + 1].v ? i + 1 : succ[i + 1];
		for (int pid = L - 1; pid >= 0; --pid)
		{
			const int p = P[pid];
			Z y = f(p);
			{
				int j = succ[0], k = succ[0];
				for (int X = R2 / p; j <= X; j = succ[j])
				{
					sub(ds.sv[j * p], ds.sv[j], y);
					while (succ[k] < j * p)
						k = succ[k];
					// assert(succ[k] == j * p);
					succ[k] = succ[j * p];
				}
				for (uint64 Nx = N / p; j <= R2; j = succ[j])
					sub(ds.lv[_udiv64(Nx, j)], ds.sv[j], y);
			}
			{
				int j = R2 / p, k = R2;
				for (; j; --j)
					for (; k >= j * p; --k)
						if (ds.lv[k].v)
							sub(ds.lv[j], ds.lv[k], y);
			}
		}
		ds.partial_sum();
		return ds;
	};
	
	auto attach_small_inv = [&](DS &ds, const std::function<Z (uint)> &f) -> DS & // no small p in `ds`! // 未经测试
	{
		ds.adjacent_difference();
		std::vector<int> succ(1 + R2 + 1);
		succ[R2] = R2 + 1;
		for (int i = R2 - 1; i >= 0; --i)
			succ[i] = ds.sv[i + 1].v ? i + 1 : succ[i + 1];
		for (int pid = 0; pid < L; ++pid)
		{
			const int p = P[pid];
			Z y = f(p);
			{
				int j = succ[0], k = succ[0];
				for (int X = R2 / p; j <= X; j = succ[j])
				{
					sub(ds.sv[j * p], ds.sv[j], y);
					while (succ[k] < j * p)
						k = succ[k];
					// assert(succ[k] != j * p);
					succ[j * p] = succ[k], succ[k] = j * p;
				}
				for (uint64 Nx = N / p; j <= R2; j = succ[j])
					sub(ds.lv[_udiv64(Nx, j)], ds.sv[j], y);
			}
			{
				int j = R2 / p, k = R2;
				for (; j; --j)
					for (; k >= j * p; --k)
						if (ds.lv[k].v)
							sub(ds.lv[j], ds.lv[k], y);
			}
		}
		ds.partial_sum();
		return ds;
	};
	
	auto eliminate_small_inv = [&](DS &ds, const std::function<Z (uint)> &f) // no small p in `res / f`!
	{
		ds.adjacent_difference();
		std::vector<int> pred(1 + R2 + 1);
		pred[1] = 0;
		for (int i = 2; i <= R2 + 1; ++i)
			pred[i] = ds.sv[i - 1].v ? i - 1 : pred[i - 1];
		for (int pid = 0; pid < L; ++pid)
		{
			const int p = P[pid];
			Z y = f(p);
			{
				int j = 1, k = p;
				for (; (j + 1) * p - 1 <= R2; ++j)
					for (; k != (j + 1) * p; ++k)
						if (ds.lv[k].v)
							add(ds.lv[j], ds.lv[k], y);
				for (; k <= R2; ++k)
					if (ds.lv[k].v)
						add(ds.lv[j], ds.lv[k], y);
			}
			{
				int j = pred[R2 + 1];
				uint64 Nx = N / p;
				for (int X = R2 / p; j > X; j = pred[j])
					add(ds.lv[_udiv64(Nx, j)], ds.sv[j], y);
				int k = R2 + 1;
				for (; j; j = pred[j])
				{
					while (pred[k] > j * p)
						k = pred[k];
					// assert(pred[k] == j * p);
					pred[k] = pred[j * p];
					add(ds.sv[j * p], ds.sv[j], y);
				}
			}
		}
		ds.partial_sum();
		return ds;
	};
	
	auto calc_medium = [&](const std::function<Z (uint)> &f)
	{
		DS l;
		for (int pid = L; pid != P.size(); ++pid)
		{
			const int p = P[pid];
			const Z y = f(p);
			
			int E = 1;
			Z yp = y;
			for (uint64 pp = p; pp <= N; pp *= p, yp *= -y, ++E)
				l[pp] += yp * _Rec[E];
		}
		l.partial_sum();
		
		DS res = l;
		for (int i = 1; i <= R2; ++i)
			res.sv[i] += 1, res.lv[i] += 1;
		DS lp = l * l;
		Z r = _Rec[2];
		for (int i = 2; i <= 5; ++i)
		{
			for (int j = 1; j <= R2; ++j)
				add(res.sv[j], lp.sv[j], r), add(res.lv[j], lp.lv[j], r);
			if (i != 5)
			{
				lp = lp * l;
				r *= _Rec[i + 1];
			}
		}
		return res;
	};
	
	auto calc_large = [&](const std::function<Z (uint64)> &f, const std::function<Z (uint64)> &ps)
	{
		auto fp = [&](uint p) { return f(p); };
		auto fpe = [&](uint64 pp, uint p, uint e) { return f(pp); };
		
		DS ds = calc_medium(fp);
		ds = attach_powerful(attach_small(ds, fp), fpe);
		DS res;
		for (int i = R2; i >= 1; --i)
		{
			Z x = ps(N / i) - ds.lv[i];
			for (int j = 2; i * j <= R2; ++j)
				sub(x, f(j), res.lv[i * j]);
			res.lv[i] = x;
		}
		return res;
	};
	
	auto mult_large = [&](DS &&ds, const DS &l)
	{
		for (int i = 1; i <= R2; ++i)
		{
			Z &x = ds.lv[i];
			for (int j = 1; i * j <= R2; ++j)
				if (ds.sv[j] != ds.sv[j - 1])
					add(x, ds.sv[j] - ds.sv[j - 1], l.lv[i * j]);
		}
		return ds;
	};
	DS l0 = calc_large(
		[&](uint64 n) { return 1; },
		[&](uint64 n) { return Z(n % Mod); }
	);
	DS l1 = calc_large(
		[&](uint64 n) { return Z(n % Mod); },
		[&](uint64 n) { return n %= Mod, Z(n * (n + 1) / 2 % Mod); }
	);
	DS l;
	for (int i = 1; i <= R2; ++i)
		l.lv[i] = A * l0.lv[i] + B * l1.lv[i];
	
	auto fp = [&](uint p) { return A + B * p; };
	auto fpe = [&](uint64 pp, uint p, uint e) { return A * e + B * p; };
	
	DS res = mult_large(calc_medium(fp), l);
	return attach_powerful(attach_small(res, fp), fpe);
}

#include <ctime>

int main(int argc, char **argv)
{
	int T;
	scanf("%u", &T);
	while (T--)
	{
		uint64 n;
		Z a, b;
		
		scanf("%llu %u %u", &n, &a.v, &b.v);
		
		DS ds = calc(n, a, b);
		
		std::vector<Z> res(ds.sv.begin() + 1, ds.sv.end());
		res.insert(res.end(), ds.lv.begin() + 1, ds.lv.end());
		std::sort(res.begin(), res.end(), [](const Z a, const Z b) { return a.v < b.v; });
		res.erase(std::unique(res.begin(), res.end()), res.end());
		uint Ans = 0;
		for (auto x : res)
			Ans ^= x.v;
		printf("%u\n", Ans);
	}
	fprintf(stderr, "%ld\n", clock());
	
	return 0;
}
/*

























































































































































#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
using LL = long long;

const int maxn = 4e5 + 5;
const LL INF = 1e18;

struct Point{
    LL a, b;

    Point(LL a = 0, LL b = INF) : a(a), b(b) {}

    LL val(LL x){
        return a * x + b;
    }

    Point operator-(Point t){
        return {a - t.a, b - t.b};
    }

};

int sign(__int128_t t){
    if (t > 0) return 1;
    if (t < 0) return -1;
    return 0;
}

int check(Point a, Point b){
    return sign(__int128_t(a.a) * b.b - __int128_t(a.b) * b.a);
}

int check(Point a, Point b, Point c){
    return check(b - a, c - b);
}

namespace SGT{

vector<Point> tr[maxn * 4];
int pt[maxn * 4];

void modify(int u, int l, int r, int x, Point line){
    while(tr[u].size() >= 2 and check(tr[u][tr[u].size() - 2], tr[u].back(), line) >= 0){
        tr[u].pop_back();
    }
    tr[u].push_back(line);
    if (l == r) return;
    int mid = (l + r) / 2;
    if (x <= mid) modify(2 * u, l, mid, x, line);
    else modify(2 * u + 1, mid + 1, r, x, line);
}

LL query(int u, LL x){
    while(pt[u] + 1 < tr[u].size() and tr[u][pt[u]].val(x) >= tr[u][pt[u] + 1].val(x)){
        pt[u]++;
    }
    return tr[u][pt[u]].val(x);
}

LL query(int u, int l, int r, int L, int R, LL x){
    if (l > R or r < L) return INF;
    if (l >= L and r <= R){
        return query(u, x);
    }
    int mid = (l + r) / 2;
    return min(query(2 * u, l, mid, L, R, x), query(2 * u + 1, mid + 1, r, L, R, x));
}

}

namespace Convex{

Point stk[maxn];
int top;

struct Event{
    int top, pos;
    Point p;
};

vector<Event> ops;

void push_back(Point line){
    if (top <= 1){
        ops.push_back({top, top + 1, stk[top + 1]});
        stk[++top] = line;
        return;
    }
    int l = 2, r = top + 1;
    while(l < r){
        int mid = (l + r + 1) / 2;
        if (check(stk[mid - 2], stk[mid - 1], line) >= 0) r = mid - 1;
        else l = mid;
    }
    ops.push_back({top, r, stk[r]});
    stk[top = r] = line;
}

void undo(){
    auto [_top, pos, p] = ops.back();
    ops.pop_back();
    top = _top;
    stk[pos] = p;
}

LL query(LL x){
    int l = 1, r = top;
    while(l < r){
        int mid = (l + r) / 2;
        if (stk[mid + 1].val(x) <= stk[mid].val(x)) l = mid + 1;
        else r = mid;
    }
    return stk[r].val(x);
}

}

LL dp[maxn], x[maxn], y[maxn];
pair<LL, LL> p[maxn];

int main(){

#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif

    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    int n, k;
    cin >> n >> k;
    for(int i = 1; i <= n; i++){
        cin >> p[i].first >> p[i].second;
    }
    sort(p + 1, p + n + 1);
    for(int i = 1; i <= n; i++){
        tie(x[i], y[i]) = p[i];
    }
    // for(int i = 1; i <= n; i++){
    //     cout << x[i] << ' ' << y[i] << '\n';
    // }
    y[0] = INF;
    vector<int> stk{0};
    for(int i = 1; i <= n; i++){
        while(y[stk.back()] <= y[i]){
            Convex::undo();
            stk.pop_back();
        }
        SGT::modify(1, 1, n, i, {k - x[i], dp[i - 1]});
        Point line = {y[i], SGT::query(1, 1, n, stk.back() + 1, i, y[i])};
        Convex::push_back(line);
        dp[i] = Convex::query(x[i]);
        stk.push_back(i);
    }
    // for(int i = 1; i <= n; i++){
    //     cout << dp[i] << '\n';
    // }
    cout << dp[n] << '\n';

}#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
using LL = long long;

const int maxn = 4e5 + 5;
const LL INF = 1e18;

struct Point{
    LL a, b;

    Point(LL a = 0, LL b = INF) : a(a), b(b) {}

    LL val(LL x){
        return a * x + b;
    }

    Point operator-(Point t){
        return {a - t.a, b - t.b};
    }

};

int sign(__int128_t t){
    if (t > 0) return 1;
    if (t < 0) return -1;
    return 0;
}

int check(Point a, Point b){
    return sign(__int128_t(a.a) * b.b - __int128_t(a.b) * b.a);
}

int check(Point a, Point b, Point c){
    return check(b - a, c - b);
}

namespace SGT{

vector<Point> tr[maxn * 4];
int pt[maxn * 4];

void modify(int u, int l, int r, int x, Point line){
    while(tr[u].size() >= 2 and check(tr[u][tr[u].size() - 2], tr[u].back(), line) >= 0){
        tr[u].pop_back();
    }
    tr[u].push_back(line);
    if (l == r) return;
    int mid = (l + r) / 2;
    if (x <= mid) modify(2 * u, l, mid, x, line);
    else modify(2 * u + 1, mid + 1, r, x, line);
}

LL query(int u, LL x){
    while(pt[u] + 1 < tr[u].size() and tr[u][pt[u]].val(x) >= tr[u][pt[u] + 1].val(x)){
        pt[u]++;
    }
    return tr[u][pt[u]].val(x);
}

LL query(int u, int l, int r, int L, int R, LL x){
    if (l > R or r < L) return INF;
    if (l >= L and r <= R){
        return query(u, x);
    }
    int mid = (l + r) / 2;
    return min(query(2 * u, l, mid, L, R, x), query(2 * u + 1, mid + 1, r, L, R, x));
}

}

namespace Convex{

Point stk[maxn];
int top;

struct Event{
    int top, pos;
    Point p;
};

vector<Event> ops;

void push_back(Point line){
    if (top <= 1){
        ops.push_back({top, top + 1, stk[top + 1]});
        stk[++top] = line;
        return;
    }
    int l = 2, r = top + 1;
    while(l < r){
        int mid = (l + r + 1) / 2;
        if (check(stk[mid - 2], stk[mid - 1], line) >= 0) r = mid - 1;
        else l = mid;
    }
    ops.push_back({top, r, stk[r]});
    stk[top = r] = line;
}

void undo(){
    auto [_top, pos, p] = ops.back();
    ops.pop_back();
    top = _top;
    stk[pos] = p;
}

LL query(LL x){
    int l = 1, r = top;
    while(l < r){
        int mid = (l + r) / 2;
        if (stk[mid + 1].val(x) <= stk[mid].val(x)) l = mid + 1;
        else r = mid;
    }
    return stk[r].val(x);
}

}

LL dp[maxn], x[maxn], y[maxn];
pair<LL, LL> p[maxn];

int main(){

#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif

    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    int n, k;
    cin >> n >> k;
    for(int i = 1; i <= n; i++){
        cin >> p[i].first >> p[i].second;
    }
    sort(p + 1, p + n + 1);
    for(int i = 1; i <= n; i++){
        tie(x[i], y[i]) = p[i];
    }
    // for(int i = 1; i <= n; i++){
    //     cout << x[i] << ' ' << y[i] << '\n';
    // }
    y[0] = INF;
    vector<int> stk{0};
    for(int i = 1; i <= n; i++){
        while(y[stk.back()] <= y[i]){
            Convex::undo();
            stk.pop_back();
        }
        SGT::modify(1, 1, n, i, {k - x[i], dp[i - 1]});
        Point line = {y[i], SGT::query(1, 1, n, stk.back() + 1, i, y[i])};
        Convex::push_back(line);
        dp[i] = Convex::query(x[i]);
        stk.push_back(i);
    }
    // for(int i = 1; i <= n; i++){
    //     cout << dp[i] << '\n';
    // }
    cout << dp[n] << '\n';

}#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
using LL = long long;

const int maxn = 4e5 + 5;
const LL INF = 1e18;

struct Point{
    LL a, b;

    Point(LL a = 0, LL b = INF) : a(a), b(b) {}

    LL val(LL x){
        return a * x + b;
    }

    Point operator-(Point t){
        return {a - t.a, b - t.b};
    }

};

int sign(__int128_t t){
    if (t > 0) return 1;
    if (t < 0) return -1;
    return 0;
}

int check(Point a, Point b){
    return sign(__int128_t(a.a) * b.b - __int128_t(a.b) * b.a);
}

int check(Point a, Point b, Point c){
    return check(b - a, c - b);
}

namespace SGT{

vector<Point> tr[maxn * 4];
int pt[maxn * 4];

void modify(int u, int l, int r, int x, Point line){
    while(tr[u].size() >= 2 and check(tr[u][tr[u].size() - 2], tr[u].back(), line) >= 0){
        tr[u].pop_back();
    }
    tr[u].push_back(line);
    if (l == r) return;
    int mid = (l + r) / 2;
    if (x <= mid) modify(2 * u, l, mid, x, line);
    else modify(2 * u + 1, mid + 1, r, x, line);
}

LL query(int u, LL x){
    while(pt[u] + 1 < tr[u].size() and tr[u][pt[u]].val(x) >= tr[u][pt[u] + 1].val(x)){
        pt[u]++;
    }
    return tr[u][pt[u]].val(x);
}

LL query(int u, int l, int r, int L, int R, LL x){
    if (l > R or r < L) return INF;
    if (l >= L and r <= R){
        return query(u, x);
    }
    int mid = (l + r) / 2;
    return min(query(2 * u, l, mid, L, R, x), query(2 * u + 1, mid + 1, r, L, R, x));
}

}

namespace Convex{

Point stk[maxn];
int top;

struct Event{
    int top, pos;
    Point p;
};

vector<Event> ops;

void push_back(Point line){
    if (top <= 1){
        ops.push_back({top, top + 1, stk[top + 1]});
        stk[++top] = line;
        return;
    }
    int l = 2, r = top + 1;
    while(l < r){
        int mid = (l + r + 1) / 2;
        if (check(stk[mid - 2], stk[mid - 1], line) >= 0) r = mid - 1;
        else l = mid;
    }
    ops.push_back({top, r, stk[r]});
    stk[top = r] = line;
}

void undo(){
    auto [_top, pos, p] = ops.back();
    ops.pop_back();
    top = _top;
    stk[pos] = p;
}

LL query(LL x){
    int l = 1, r = top;
    while(l < r){
        int mid = (l + r) / 2;
        if (stk[mid + 1].val(x) <= stk[mid].val(x)) l = mid + 1;
        else r = mid;
    }
    return stk[r].val(x);
}

}

LL dp[maxn], x[maxn], y[maxn];
pair<LL, LL> p[maxn];

int main(){

#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif

    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    int n, k;
    cin >> n >> k;
    for(int i = 1; i <= n; i++){
        cin >> p[i].first >> p[i].second;
    }
    sort(p + 1, p + n + 1);
    for(int i = 1; i <= n; i++){
        tie(x[i], y[i]) = p[i];
    }
    // for(int i = 1; i <= n; i++){
    //     cout << x[i] << ' ' << y[i] << '\n';
    // }
    y[0] = INF;
    vector<int> stk{0};
    for(int i = 1; i <= n; i++){
        while(y[stk.back()] <= y[i]){
            Convex::undo();
            stk.pop_back();
        }
        SGT::modify(1, 1, n, i, {k - x[i], dp[i - 1]});
        Point line = {y[i], SGT::query(1, 1, n, stk.back() + 1, i, y[i])};
        Convex::push_back(line);
        dp[i] = Convex::query(x[i]);
        stk.push_back(i);
    }
    // for(int i = 1; i <= n; i++){
    //     cout << dp[i] << '\n';
    // }
    cout << dp[n] << '\n';

}

*/