把每个质因子扒出来乱搞一下
#include <bits/stdc++.h>
using namespace std;
int g[505][505];
int isp[505];
struct Biguint {
int a[10005], len;
Biguint() {
memset(a, 0, sizeof a);
len = 0;
}
void read() {
string str;
cin >> str;
memset(a, 0, sizeof a);
len = str.length();
for (int i = 0; i < str.size(); i++)
a[i] = str[str.length() - i - 1] - '0';
}
void print() {
for (int i = len - 1; i >= 0; i--) {
cout << a[i];
}
}
bool operator < (const Biguint& obj) {
const int* b = obj.a;
if (this->len == obj.len) {
for (int i = 0; i < len; i++)
if (a[i] != b[i]) return a[i] < b[i];
return false;
}
else return this->len < obj.len;
}
bool operator > (const Biguint& obj) {
const int* b = obj.a;
if (this->len == obj.len) {
for (int i = 0; i < len; i++)
if (a[i] != b[i]) return a[i] > b[i];
return false;
}
else return this->len > obj.len;
}
bool operator != (const Biguint& obj) {
return (*this < obj) | (*this > obj);
}
bool operator == (const Biguint& obj) {
return !((*this < obj) | (*this > obj));
}
bool operator <= (const Biguint& obj) {
return (*this) < obj || (*this) == obj;
}
bool operator >= (const Biguint& obj) {
return (*this) > obj || (*this) == obj;
}
Biguint operator += (const Biguint& obj) {
const int* b = obj.a;
if (obj.len > len) len = obj.len;
for (int i = 0; i < len; i++) {
a[i] += b[i];
if (a[i] >= 10) a[i + 1] += a[i] / 10, a[i] %= 10;
}
if (a[len]) ++len;
while (a[len - 1] >= 10)
a[len] += a[len - 1] / 10, a[len - 1] %= 10, ++len;
return *this;
}
Biguint operator + (const Biguint& obj) {
Biguint ret;
ret += *this;
ret += obj;
return ret;
}
Biguint operator -= (const Biguint& obj) {
const int* b = obj.a;
for (int i = 0; i < len; i++) {
a[i] -= b[i];
if (a[i] < 0) a[i + 1]--, a[i] += 10;
}
while (a[len - 1] == 0 && len > 0) --len;
return *this;
}
Biguint operator -(const Biguint& obj) {
Biguint ret;
ret += *this;
ret -= obj;
return ret;
}
Biguint operator *= (int b) {
for (int i = 0; i < len; i++)
a[i] *= b;
for (int i = 0; i < len; i++)
a[i + 1] += a[i] / 10, a[i] %= 10;
++len;
while (a[len - 1] >= 10)
a[len] += a[len - 1] / 10, a[len - 1] %= 10, ++len;
while (a[len - 1] == 0 && len > 0) --len;
return *this;
}
Biguint operator * (int b) {
Biguint ret;
ret = *this;
ret *= b;
return ret;
}
Biguint operator * (const Biguint& obj) {
const int* b = obj.a;
Biguint ret;
for (int i = 0; i < len; i++)
for (int j = 0; j < obj.len; j++)
ret.a[i + j] += a[i] * b[j];
for (int i = 0; i < len + obj.len; i++)
ret.a[i + 1] += ret.a[i] / 10, ret.a[i] %= 10;
ret.len = len + obj.len;
++ret.len;
while (ret.a[ret.len - 1])
ret.a[ret.len] += ret.a[ret.len - 1] / 10, ret.a[ret.len - 1] %= 10, ++ret.len;
while (ret.a[ret.len - 1] == 0 && ret.len > 0) --ret.len;
return ret;
}
};
ostream& operator << (ostream& os, Biguint num)
{
//cout << "[" << num.len << "]";
for (int i = num.len - 1; i >= 0; --i)
os << num.a[i];
if (num.len == 0) os << "0";
return os;
}
istream& operator >> (istream& is, Biguint& num)
{
string str;
is >> str;
memset(num.a, 0, sizeof num.a);
num.len = str.length();
for (int i = 0; i < str.length(); i++)
num.a[i] = str[str.length() - i - 1] - '0';
return is;
}
Biguint bigu(int t) {
Biguint b;
b.len = 1;
b.a[0] = 1;
b*=t;
return b;
}
int main() {
isp[1]=0;
for(int i=2;i<=500;i++) {
int flag=1;
for(int j=2;j<i;j++)
if(i%j==0) flag=0;
isp[i]=flag;
}
for(int i=1;i<=500;i++) {
int t=i;
for(int j=2;j<=i;j++)
while(isp[j]&&t%j==0)
g[i][j]++,t/=j;
}
int T;
cin>>T;
while(T--) {
int n,k;
cin>>n>>k;
int tk=k;
int myFac[505]={};
for(int i=2;i<=k;i++) {
while(isp[i]&&tk%i==0)
myFac[i]++,tk/=i;
}
int aFac[505]={};
for(int i=k*2;i<=n;i+=k) {
for(int j=2;j<=i;j++)
if(g[i][j]>myFac[j]) aFac[j]=1;
}
for(int i=2;i<=n;i++) {
myFac[i]+=aFac[i];
//cout<<myFac[i]<<" ";
}
//cout<<endl;
Biguint ans = bigu(1);
for(int i=2;i<=n;i++) {
while(myFac[i]) {
Biguint x = bigu(i);
ans=ans*x;
myFac[i]--;
}
}
cout<<ans<<endl;
}
}