#include <iostream>
#include <math.h>
#include <algorithm>

using namespace std;

long long logs[10];
unsigned int cur;
unsigned int a, b;
long long ans;

unsigned int nextRand24() {
  cur = cur * a + b;
  return cur >> 8;
}

unsigned int nextRand32() {
  unsigned int a = nextRand24(), b = nextRand24();
  return (a << 8) ^ b;
}

void countSort(long long lol[], int n, int it) {
	long long out[n];
	long long i, c[8] = {0};
    for (i = 0; i < n; i++)
		c[(lol[i]>>it) & 7]++;
    for (i = 1; i < 8; i++)
		c[i] += c[i - 1];
    for (i = n - 1; i >= 0; i--) {
		out[c[(lol[i]>>it) & 7] - 1] = lol[i];
		c[(lol[i]>>it) & 7]--;
	}
	for (i = 0; i < n; i++)
		lol[i] = out[i];
}

void radixsort(long long lol[], int n) {
	long long maxi = -1e9;
	int i;
	for (i = 0; i < n; i++) {
        if (lol[i] > maxi) maxi = lol[i];
	}
	i = 3 * (lower_bound(logs, logs + 10, maxi) - logs + 1);
	for (int it = 0; it < i; it += 3)
		countSort(lol, n, it);
}

int main() {
    //freopen("input.in", "r", stdin);
    //freopen("out.out", "w", stdout);
    int t, n;
    cin >> t >> n;
    long long kek[n];
    logs[0] = 1;
    for (int i = 1; i < 10; i++) logs[i] = logs[i - 1]<<3;
    for (int i = 0; i < t; i++) {
        cin >> a >> b;
        for (int j = 0; j < n; j++) kek[j] = nextRand32();
        radixsort(kek, n);
        ans = 0;
        for (int j = 0; j < n; j++) ans += (j + 1) * kek[j];
        cout << ans << '\n';
    }
    return 0;
}