#include <bits/stdc++.h> using namespace std; typedef long long LL; const int N = 1e7 + 9; int mn[N]; vector<int> pri; bitset<N> vis; void init() { mn[1] = 1; for (int i = 2; i <= 1e7; i++) { if (!vis[i]) mn[i] = i, pri.push_back(i); for (int j : pri) { if (i * j > 1e7) break; vis[i * j] = 1, mn[i * j] = j; if (i % j == 0) break; } } } int get(int p, int r) { if (p % 4 == 1) return (r ? p - 1 : 2 * p - 1); else return (r ? p + 1 : 1); } int _, p, r; signed main() { init(); scanf("%d", &_); while (_--) { scanf("%d%d", &p, &r); LL ans = 1; while (p > 1) { ans *= get(mn[p], r % mn[p]); p /= mn[p]; } printf("%lld\n", ans); } return 0; }