#include <bits/stdc++.h>
using namespace std;
int main() {
  long long n, q, a, b, a2, b2, res = -1;
  cin >> n >> q;
  if (n % 2 == 0) {
    for (long long i = 0; i < q; i++) {
      cin >> a2 >> b2;
      a = a2 - 1;
      b = b2 - 1;
      res = -1;
      if ((a + b) % 2 == 0) {
        res = ((a * (n / 2)) + ((b / 2) + 1));
        cout << res << "\n";
      }
      if ((a + b) % 2 != 0) {
        res = (((n * n) / 2) + (a * (n / 2)) + ((b / 2) + 1));
        cout << res << "\n";
      }
    }
  }
  if (n % 2 == 1) {
    for (long long i = 0; i < q; i++) {
      cin >> a2 >> b2;
      a = a2 - 1;
      b = b2 - 1;
      res = -1;
      if ((a + b) % 2 == 0) {
        if (a % 2 == 0) {
          res = ((n * (a / 2)) + ((b / 2) + 1));
          cout << res << "\n";
        }
        if (a % 2 != 0) {
          res = ((n * ((a - 1) / 2)) + ((n + 1) / 2) + ((b / 2) + 1));
          cout << res << "\n";
        }
      }
      if ((a + b) % 2 != 0) {
        if (a % 2 == 0) {
          res = ((((n * n) / 2) + 1) + (n * (a / 2)) + ((b / 2) + 1));
          cout << res << "\n";
        }
        if (a % 2 != 0) {
          res = ((((n * n) / 2) + 1) + (n * ((a - 1) / 2)) + (n / 2) +
                 ((b / 2) + 1));
          cout << res << "\n";
        }
      }
    }
  }
  return 0;
}
