#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<string>
#include<map>
#include<set>
#include<vector>
#include<cassert>
#define LL long long
#define LD double
#define inf 10000000000000000ll
#define lowbit(x) ((x)&(-(x)))
using namespace std;
long long gcd(long long a,long long b)
{
    if (!a) return b;
    if (!b) return a;
    return gcd(b,a%b);
}
long long a[40][40],sum[40][40];
int main()//LL
{
a[0][0]=7225456;
a[0][1]=16998968;
a[0][2]=26608262;
a[0][3]=36255690;
a[0][4]=45816146;
a[0][5]=55370630;
a[0][6]=65165462;
a[0][7]=74300494;
a[0][8]=84301258;
a[0][9]=92966972;
a[0][10]=101890498;
a[0][11]=113072232;
a[0][12]=122515730;
a[0][13]=131623796;
a[0][14]=140865306;
a[0][15]=148097804;
a[0][16]=160747616;
a[0][17]=168714532;
a[0][18]=176781172;
a[0][19]=185326212;
a[0][20]=192972596;
a[0][21]=203055312;
a[0][22]=217880224;
a[0][23]=225804854;
a[0][24]=236683470;
a[0][25]=243911430;
a[0][26]=251946134;
a[0][27]=263769424;
a[0][28]=272237752;
a[0][29]=279477792;
a[0][30]=958036;
a[1][0]=16998968;
a[1][1]=1475588;
a[1][2]=36930012;
a[1][3]=1769574;
a[1][4]=55736788;
a[1][5]=2974820;
a[1][6]=73854534;
a[1][7]=5178186;
a[1][8]=90648184;
a[1][9]=8277820;
a[1][10]=104245530;
a[1][11]=14732438;
a[1][12]=119782020;
a[1][13]=19301554;
a[1][14]=132909790;
a[1][15]=26433836;
a[1][16]=143030526;
a[1][17]=36404324;
a[1][18]=150418636;
a[1][19]=49079346;
a[1][20]=151196650;
a[1][21]=68345194;
a[1][22]=155710048;
a[1][23]=83962088;
a[1][24]=162802566;
a[1][25]=97094410;
a[1][26]=163769742;
a[1][27]=116198722;
a[1][28]=165673236;
a[1][29]=134347102;
a[1][30]=2546;
a[2][0]=26608262;
a[2][1]=36930012;
a[2][2]=2097524;
a[2][3]=1169298;
a[2][4]=65307556;
a[2][5]=75835420;
a[2][6]=5014634;
a[2][7]=1383964;
a[2][8]=99748144;
a[2][9]=113729874;
a[2][10]=12685406;
a[2][11]=1097928;
a[2][12]=128209246;
a[2][13]=153102134;
a[2][14]=24862722;
a[2][15]=1243418;
a[2][16]=150776172;
a[2][17]=190636222;
a[2][18]=44941988;
a[2][19]=1105870;
a[2][20]=157694762;
a[2][21]=225264932;
a[2][22]=83363214;
a[2][23]=1234156;
a[2][24]=168651368;
a[2][25]=266973384;
a[2][26]=110946504;
a[2][27]=1133158;
a[2][28]=170739222;
a[2][29]=302933962;
a[2][30]=1038622;
a[3][0]=36255690;
a[3][1]=1769574;
a[3][2]=1169298;
a[3][3]=1903212;
a[3][4]=74915244;
a[3][5]=4671760;
a[3][6]=1375670;
a[3][7]=1287224;
a[3][8]=108807908;
a[3][9]=11134242;
a[3][10]=1101828;
a[3][11]=1172860;
a[3][12]=136747156;
a[3][13]=23821166;
a[3][14]=1289808;
a[3][15]=1442786;
a[3][16]=158582584;
a[3][17]=42544140;
a[3][18]=1109766;
a[3][19]=1070254;
a[3][20]=164389788;
a[3][21]=77200584;
a[3][22]=1190926;
a[3][23]=1280924;
a[3][24]=174589416;
a[3][25]=107567802;
a[3][26]=1115378;
a[3][27]=1276202;
a[3][28]=175893162;
a[3][29]=146881048;
a[3][30]=3524;
a[4][0]=45816146;
a[4][1]=55736788;
a[4][2]=65307556;
a[4][3]=74915244;
a[4][4]=5416476;
a[4][5]=1110390;
a[4][6]=1369920;
a[4][7]=1296918;
a[4][8]=117837898;
a[4][9]=130961138;
a[4][10]=139665598;
a[4][11]=151526242;
a[4][12]=23888710;
a[4][13]=1347552;
a[4][14]=1338360;
a[4][15]=1296602;
a[4][16]=166163902;
a[4][17]=206475016;
a[4][18]=214211504;
a[4][19]=222625176;
a[4][20]=70498632;
a[4][21]=1256102;
a[4][22]=1151290;
a[4][23]=1400386;
a[4][24]=180395886;
a[4][25]=281521620;
a[4][26]=289254726;
a[4][27]=301493220;
a[4][28]=143550506;
a[4][29]=1293210;
a[4][30]=5542;
a[5][0]=55370630;
a[5][1]=2974820;
a[5][2]=75835420;
a[5][3]=4671760;
a[5][4]=1110390;
a[5][5]=2366272;
a[5][6]=1212114;
a[5][7]=1483050;
a[5][8]=126924744;
a[5][9]=15125160;
a[5][10]=138725038;
a[5][11]=23843204;
a[5][12]=1264250;
a[5][13]=1221990;
a[5][14]=1257914;
a[5][15]=1804020;
a[5][16]=173996140;
a[5][17]=50349426;
a[5][18]=179271378;
a[5][19]=65415366;
a[5][20]=1242652;
a[5][21]=1140104;
a[5][22]=1092940;
a[5][23]=1303244;
a[5][24]=186272632;
a[5][25]=120213614;
a[5][26]=185279106;
a[5][27]=141683634;
a[5][28]=1205168;
a[5][29]=1299282;
a[5][30]=3012;
a[6][0]=65165462;
a[6][1]=73854534;
a[6][2]=5014634;
a[6][3]=1375670;
a[6][4]=1369920;
a[6][5]=1212114;
a[6][6]=2734960;
a[6][7]=1303834;
a[6][8]=136432448;
a[6][9]=147359196;
a[6][10]=21826562;
a[6][11]=1215420;
a[6][12]=1366610;
a[6][13]=1241714;
a[6][14]=1227908;
a[6][15]=1274780;
a[6][16]=182393466;
a[6][17]=221496738;
a[6][18]=61784780;
a[6][19]=1214940;
a[6][20]=1265992;
a[6][21]=1315942;
a[6][22]=1307572;
a[6][23]=1541806;
a[6][24]=193314760;
a[6][25]=295140662;
a[6][26]=137431424;
a[6][27]=1292282;
a[6][28]=1302392;
a[6][29]=1305934;
a[6][30]=4120;
a[7][0]=74300494;
a[7][1]=5178186;
a[7][2]=1383964;
a[7][3]=1287224;
a[7][4]=1296918;
a[7][5]=1483050;
a[7][6]=1303834;
a[7][7]=3127252;
a[7][8]=144493786;
a[7][9]=20047268;
a[7][10]=1249286;
a[7][11]=1507462;
a[7][12]=1297798;
a[7][13]=1740900;
a[7][14]=1438628;
a[7][15]=1304676;
a[7][16]=188626972;
a[7][17]=59098376;
a[7][18]=1199350;
a[7][19]=1297880;
a[7][20]=1161460;
a[7][21]=1335056;
a[7][22]=1357426;
a[7][23]=1324796;
a[7][24]=197180694;
a[7][25]=133847340;
a[7][26]=1180614;
a[7][27]=1271002;
a[7][28]=1332654;
a[7][29]=1444776;
a[7][30]=3550;
a[8][0]=84301258;
a[8][1]=90648184;
a[8][2]=99748144;
a[8][3]=108807908;
a[8][4]=117837898;
a[8][5]=126924744;
a[8][6]=136432448;
a[8][7]=144493786;
a[8][8]=22915724;
a[8][9]=1092744;
a[8][10]=1270844;
a[8][11]=1105474;
a[8][12]=1478046;
a[8][13]=1468280;
a[8][14]=1249458;
a[8][15]=1258932;
a[8][16]=197796356;
a[8][17]=234146158;
a[8][18]=241225774;
a[8][19]=249027950;
a[8][20]=255677072;
a[8][21]=265714748;
a[8][22]=282082890;
a[8][23]=289001962;
a[8][24]=136259942;
a[8][25]=1478446;
a[8][26]=1712688;
a[8][27]=1080956;
a[8][28]=1292566;
a[8][29]=1394582;
a[8][30]=2594;
a[9][0]=92966972;
a[9][1]=8277820;
a[9][2]=113729874;
a[9][3]=11134242;
a[9][4]=130961138;
a[9][5]=15125160;
a[9][6]=147359196;
a[9][7]=20047268;
a[9][8]=1092744;
a[9][9]=3350172;
a[9][10]=1024520;
a[9][11]=1231800;
a[9][12]=1279850;
a[9][13]=1412774;
a[9][14]=1366560;
a[9][15]=1410658;
a[9][16]=203478908;
a[9][17]=70172978;
a[9][18]=206929544;
a[9][19]=87747274;
a[9][20]=202114950;
a[9][21]=113715946;
a[9][22]=203218678;
a[9][23]=133898688;
a[9][24]=1286238;
a[9][25]=1788036;
a[9][26]=1353054;
a[9][27]=1670382;
a[9][28]=1770838;
a[9][29]=1406382;
a[9][30]=3880;
a[10][0]=101890498;
a[10][1]=104245530;
a[10][2]=12685406;
a[10][3]=1101828;
a[10][4]=139665598;
a[10][5]=138725038;
a[10][6]=21826562;
a[10][7]=1249286;
a[10][8]=1270844;
a[10][9]=1024520;
a[10][10]=3662264;
a[10][11]=1151708;
a[10][12]=1187374;
a[10][13]=1332146;
a[10][14]=1198656;
a[10][15]=1633292;
a[10][16]=210091158;
a[10][17]=240996634;
a[10][18]=85817900;
a[10][19]=1145374;
a[10][20]=207419850;
a[10][21]=270537540;
a[10][22]=137569048;
a[10][23]=1275656;
a[10][24]=1180574;
a[10][25]=1266250;
a[10][26]=1172718;
a[10][27]=1365954;
a[10][28]=1458150;
a[10][29]=1424638;
a[10][30]=2796;
a[11][0]=113072232;
a[11][1]=14732438;
a[11][2]=1097928;
a[11][3]=1172860;
a[11][4]=151526242;
a[11][5]=23843204;
a[11][6]=1215420;
a[11][7]=1507462;
a[11][8]=1105474;
a[11][9]=1231800;
a[11][10]=1151708;
a[11][11]=3888208;
a[11][12]=1168242;
a[11][13]=1407112;
a[11][14]=1659612;
a[11][15]=1550538;
a[11][16]=222016418;
a[11][17]=87022642;
a[11][18]=1149400;
a[11][19]=1249690;
a[11][20]=218937574;
a[11][21]=134541954;
a[11][22]=1219970;
a[11][23]=1249942;
a[11][24]=1218600;
a[11][25]=1673364;
a[11][26]=1668244;
a[11][27]=1352850;
a[11][28]=1353856;
a[11][29]=1476226;
a[11][30]=3606;
a[12][0]=122515730;
a[12][1]=119782020;
a[12][2]=128209246;
a[12][3]=136747156;
a[12][4]=23888710;
a[12][5]=1264250;
a[12][6]=1366610;
a[12][7]=1297798;
a[12][8]=1478046;
a[12][9]=1279850;
a[12][10]=1187374;
a[12][11]=1168242;
a[12][12]=4224732;
a[12][13]=1279832;
a[12][14]=1287238;
a[12][15]=1488804;
a[12][16]=229358894;
a[12][17]=253529730;
a[12][18]=259720728;
a[12][19]=266816488;
a[12][20]=125408516;
a[12][21]=1178924;
a[12][22]=1378076;
a[12][23]=1277538;
a[12][24]=1520302;
a[12][25]=1584672;
a[12][26]=1478230;
a[12][27]=1331446;
a[12][28]=1271656;
a[12][29]=1288544;
a[12][30]=3454;
a[13][0]=131623796;
a[13][1]=19301554;
a[13][2]=153102134;
a[13][3]=23821166;
a[13][4]=1347552;
a[13][5]=1221990;
a[13][6]=1241714;
a[13][7]=1740900;
a[13][8]=1468280;
a[13][9]=1412774;
a[13][10]=1332146;
a[13][11]=1407112;
a[13][12]=1279832;
a[13][13]=4415756;
a[13][14]=1266740;
a[13][15]=1270440;
a[13][16]=236270786;
a[13][17]=98145578;
a[13][18]=238030550;
a[13][19]=118766030;
a[13][20]=1167124;
a[13][21]=1365724;
a[13][22]=1188502;
a[13][23]=1407678;
a[13][24]=1406026;
a[13][25]=1333278;
a[13][26]=1367882;
a[13][27]=1434038;
a[13][28]=1487828;
a[13][29]=1181078;
a[13][30]=4336;
a[14][0]=140865306;
a[14][1]=132909790;
a[14][2]=24862722;
a[14][3]=1289808;
a[14][4]=1338360;
a[14][5]=1257914;
a[14][6]=1227908;
a[14][7]=1438628;
a[14][8]=1249458;
a[14][9]=1366560;
a[14][10]=1198656;
a[14][11]=1659612;
a[14][12]=1287238;
a[14][13]=1266740;
a[14][14]=4713332;
a[14][15]=1343214;
a[14][16]=243521870;
a[14][17]=261957290;
a[14][18]=114796604;
a[14][19]=1233636;
a[14][20]=1404858;
a[14][21]=1218122;
a[14][22]=1692572;
a[14][23]=1579658;
a[14][24]=1368704;
a[14][25]=1456592;
a[14][26]=1813402;
a[14][27]=1956258;
a[14][28]=1688198;
a[14][29]=1339638;
a[14][30]=2792;
a[15][0]=148097804;
a[15][1]=26433836;
a[15][2]=1243418;
a[15][3]=1442786;
a[15][4]=1296602;
a[15][5]=1804020;
a[15][6]=1274780;
a[15][7]=1304676;
a[15][8]=1258932;
a[15][9]=1410658;
a[15][10]=1633292;
a[15][11]=1550538;
a[15][12]=1488804;
a[15][13]=1270440;
a[15][14]=1343214;
a[15][15]=5030000;
a[15][16]=246613546;
a[15][17]=113516162;
a[15][18]=1222004;
a[15][19]=1297680;
a[15][20]=1314014;
a[15][21]=1382508;
a[15][22]=1545124;
a[15][23]=1349960;
a[15][24]=1328664;
a[15][25]=1383840;
a[15][26]=1788434;
a[15][27]=1689470;
a[15][28]=1705658;
a[15][29]=1320828;
a[15][30]=3156;
a[16][0]=160747616;
a[16][1]=143030526;
a[16][2]=150776172;
a[16][3]=158582584;
a[16][4]=166163902;
a[16][5]=173996140;
a[16][6]=182393466;
a[16][7]=188626972;
a[16][8]=197796356;
a[16][9]=203478908;
a[16][10]=210091158;
a[16][11]=222016418;
a[16][12]=229358894;
a[16][13]=236270786;
a[16][14]=243521870;
a[16][15]=246613546;
a[16][16]=123991808;
a[16][17]=1123564;
a[16][18]=1219870;
a[16][19]=1150428;
a[16][20]=1383016;
a[16][21]=1298708;
a[16][22]=1279114;
a[16][23]=1194510;
a[16][24]=1683554;
a[16][25]=1576932;
a[16][26]=1257252;
a[16][27]=1876034;
a[16][28]=1396140;
a[16][29]=1429310;
a[16][30]=3214;
a[17][0]=168714532;
a[17][1]=36404324;
a[17][2]=190636222;
a[17][3]=42544140;
a[17][4]=206475016;
a[17][5]=50349426;
a[17][6]=221496738;
a[17][7]=59098376;
a[17][8]=234146158;
a[17][9]=70172978;
a[17][10]=240996634;
a[17][11]=87022642;
a[17][12]=253529730;
a[17][13]=98145578;
a[17][14]=261957290;
a[17][15]=113516162;
a[17][16]=1123564;
a[17][17]=5471864;
a[17][18]=1191538;
a[17][19]=1198536;
a[17][20]=1131254;
a[17][21]=1409416;
a[17][22]=1142754;
a[17][23]=1247566;
a[17][24]=1304850;
a[17][25]=1781492;
a[17][26]=2087508;
a[17][27]=1241990;
a[17][28]=1328112;
a[17][29]=1417880;
a[17][30]=5944;
a[18][0]=176781172;
a[18][1]=150418636;
a[18][2]=44941988;
a[18][3]=1109766;
a[18][4]=214211504;
a[18][5]=179271378;
a[18][6]=61784780;
a[18][7]=1199350;
a[18][8]=241225774;
a[18][9]=206929544;
a[18][10]=85817900;
a[18][11]=1149400;
a[18][12]=259720728;
a[18][13]=238030550;
a[18][14]=114796604;
a[18][15]=1222004;
a[18][16]=1219870;
a[18][17]=1191538;
a[18][18]=5666072;
a[18][19]=1090840;
a[18][20]=1227450;
a[18][21]=1112624;
a[18][22]=1265258;
a[18][23]=1551586;
a[18][24]=1291072;
a[18][25]=1881208;
a[18][26]=1341552;
a[18][27]=1753004;
a[18][28]=1554168;
a[18][29]=1404154;
a[18][30]=3938;
a[19][0]=185326212;
a[19][1]=49079346;
a[19][2]=1105870;
a[19][3]=1070254;
a[19][4]=222625176;
a[19][5]=65415366;
a[19][6]=1214940;
a[19][7]=1297880;
a[19][8]=249027950;
a[19][9]=87747274;
a[19][10]=1145374;
a[19][11]=1249690;
a[19][12]=266816488;
a[19][13]=118766030;
a[19][14]=1233636;
a[19][15]=1297680;
a[19][16]=1150428;
a[19][17]=1198536;
a[19][18]=1090840;
a[19][19]=6018572;
a[19][20]=1091270;
a[19][21]=1235144;
a[19][22]=1555634;
a[19][23]=1392328;
a[19][24]=1498038;
a[19][25]=1215966;
a[19][26]=1842626;
a[19][27]=1412672;
a[19][28]=1874150;
a[19][29]=1295970;
a[19][30]=3588;
a[20][0]=192972596;
a[20][1]=151196650;
a[20][2]=157694762;
a[20][3]=164389788;
a[20][4]=70498632;
a[20][5]=1242652;
a[20][6]=1265992;
a[20][7]=1161460;
a[20][8]=255677072;
a[20][9]=202114950;
a[20][10]=207419850;
a[20][11]=218937574;
a[20][12]=125408516;
a[20][13]=1167124;
a[20][14]=1404858;
a[20][15]=1314014;
a[20][16]=1383016;
a[20][17]=1131254;
a[20][18]=1227450;
a[20][19]=1091270;
a[20][20]=6153436;
a[20][21]=1273750;
a[20][22]=1253446;
a[20][23]=1382780;
a[20][24]=1412056;
a[20][25]=1373870;
a[20][26]=1269194;
a[20][27]=1910588;
a[20][28]=1196240;
a[20][29]=1351344;
a[20][30]=4834;
a[21][0]=203055312;
a[21][1]=68345194;
a[21][2]=225264932;
a[21][3]=77200584;
a[21][4]=1256102;
a[21][5]=1140104;
a[21][6]=1315942;
a[21][7]=1335056;
a[21][8]=265714748;
a[21][9]=113715946;
a[21][10]=270537540;
a[21][11]=134541954;
a[21][12]=1178924;
a[21][13]=1365724;
a[21][14]=1218122;
a[21][15]=1382508;
a[21][16]=1298708;
a[21][17]=1409416;
a[21][18]=1112624;
a[21][19]=1235144;
a[21][20]=1273750;
a[21][21]=6405408;
a[21][22]=1118728;
a[21][23]=1349808;
a[21][24]=1305854;
a[21][25]=1444660;
a[21][26]=1454546;
a[21][27]=1302042;
a[21][28]=1356944;
a[21][29]=1203706;
a[21][30]=4494;
a[22][0]=217880224;
a[22][1]=155710048;
a[22][2]=83363214;
a[22][3]=1190926;
a[22][4]=1151290;
a[22][5]=1092940;
a[22][6]=1307572;
a[22][7]=1357426;
a[22][8]=282082890;
a[22][9]=203218678;
a[22][10]=137569048;
a[22][11]=1219970;
a[22][12]=1378076;
a[22][13]=1188502;
a[22][14]=1692572;
a[22][15]=1545124;
a[22][16]=1279114;
a[22][17]=1142754;
a[22][18]=1265258;
a[22][19]=1555634;
a[22][20]=1253446;
a[22][21]=1118728;
a[22][22]=6733748;
a[22][23]=1255016;
a[22][24]=1400382;
a[22][25]=1427928;
a[22][26]=1353746;
a[22][27]=1363774;
a[22][28]=1988704;
a[22][29]=1429282;
a[22][30]=2904;
a[23][0]=225804854;
a[23][1]=83962088;
a[23][2]=1234156;
a[23][3]=1280924;
a[23][4]=1400386;
a[23][5]=1303244;
a[23][6]=1541806;
a[23][7]=1324796;
a[23][8]=289001962;
a[23][9]=133898688;
a[23][10]=1275656;
a[23][11]=1249942;
a[23][12]=1277538;
a[23][13]=1407678;
a[23][14]=1579658;
a[23][15]=1349960;
a[23][16]=1194510;
a[23][17]=1247566;
a[23][18]=1551586;
a[23][19]=1392328;
a[23][20]=1382780;
a[23][21]=1349808;
a[23][22]=1255016;
a[23][23]=7083392;
a[23][24]=1198094;
a[23][25]=1298602;
a[23][26]=1317330;
a[23][27]=1733266;
a[23][28]=1487144;
a[23][29]=2110382;
a[23][30]=2908;
a[24][0]=236683470;
a[24][1]=162802566;
a[24][2]=168651368;
a[24][3]=174589416;
a[24][4]=180395886;
a[24][5]=186272632;
a[24][6]=193314760;
a[24][7]=197180694;
a[24][8]=136259942;
a[24][9]=1286238;
a[24][10]=1180574;
a[24][11]=1218600;
a[24][12]=1520302;
a[24][13]=1406026;
a[24][14]=1368704;
a[24][15]=1328664;
a[24][16]=1683554;
a[24][17]=1304850;
a[24][18]=1291072;
a[24][19]=1498038;
a[24][20]=1412056;
a[24][21]=1305854;
a[24][22]=1400382;
a[24][23]=1198094;
a[24][24]=7157980;
a[24][25]=1257488;
a[24][26]=1517684;
a[24][27]=1426292;
a[24][28]=1372664;
a[24][29]=1731108;
a[24][30]=7948;
a[25][0]=243911430;
a[25][1]=97094410;
a[25][2]=266973384;
a[25][3]=107567802;
a[25][4]=281521620;
a[25][5]=120213614;
a[25][6]=295140662;
a[25][7]=133847340;
a[25][8]=1478446;
a[25][9]=1788036;
a[25][10]=1266250;
a[25][11]=1673364;
a[25][12]=1584672;
a[25][13]=1333278;
a[25][14]=1456592;
a[25][15]=1383840;
a[25][16]=1576932;
a[25][17]=1781492;
a[25][18]=1881208;
a[25][19]=1215966;
a[25][20]=1373870;
a[25][21]=1444660;
a[25][22]=1427928;
a[25][23]=1298602;
a[25][24]=1257488;
a[25][25]=7423996;
a[25][26]=1305316;
a[25][27]=1196742;
a[25][28]=1214116;
a[25][29]=1206338;
a[25][30]=3676;
a[26][0]=251946134;
a[26][1]=163769742;
a[26][2]=110946504;
a[26][3]=1115378;
a[26][4]=289254726;
a[26][5]=185279106;
a[26][6]=137431424;
a[26][7]=1180614;
a[26][8]=1712688;
a[26][9]=1353054;
a[26][10]=1172718;
a[26][11]=1668244;
a[26][12]=1478230;
a[26][13]=1367882;
a[26][14]=1813402;
a[26][15]=1788434;
a[26][16]=1257252;
a[26][17]=2087508;
a[26][18]=1341552;
a[26][19]=1842626;
a[26][20]=1269194;
a[26][21]=1454546;
a[26][22]=1353746;
a[26][23]=1317330;
a[26][24]=1517684;
a[26][25]=1305316;
a[26][26]=7704136;
a[26][27]=1217878;
a[26][28]=1422876;
a[26][29]=1238042;
a[26][30]=4842;
a[27][0]=263769424;
a[27][1]=116198722;
a[27][2]=1133158;
a[27][3]=1276202;
a[27][4]=301493220;
a[27][5]=141683634;
a[27][6]=1292282;
a[27][7]=1271002;
a[27][8]=1080956;
a[27][9]=1670382;
a[27][10]=1365954;
a[27][11]=1352850;
a[27][12]=1331446;
a[27][13]=1434038;
a[27][14]=1956258;
a[27][15]=1689470;
a[27][16]=1876034;
a[27][17]=1241990;
a[27][18]=1753004;
a[27][19]=1412672;
a[27][20]=1910588;
a[27][21]=1302042;
a[27][22]=1363774;
a[27][23]=1733266;
a[27][24]=1426292;
a[27][25]=1196742;
a[27][26]=1217878;
a[27][27]=7942984;
a[27][28]=1137450;
a[27][29]=1751446;
a[27][30]=6758;
a[28][0]=272237752;
a[28][1]=165673236;
a[28][2]=170739222;
a[28][3]=175893162;
a[28][4]=143550506;
a[28][5]=1205168;
a[28][6]=1302392;
a[28][7]=1332654;
a[28][8]=1292566;
a[28][9]=1770838;
a[28][10]=1458150;
a[28][11]=1353856;
a[28][12]=1271656;
a[28][13]=1487828;
a[28][14]=1688198;
a[28][15]=1705658;
a[28][16]=1396140;
a[28][17]=1328112;
a[28][18]=1554168;
a[28][19]=1874150;
a[28][20]=1196240;
a[28][21]=1356944;
a[28][22]=1988704;
a[28][23]=1487144;
a[28][24]=1372664;
a[28][25]=1214116;
a[28][26]=1422876;
a[28][27]=1137450;
a[28][28]=8241136;
a[28][29]=1357450;
a[28][30]=3502;
a[29][0]=279477792;
a[29][1]=134347102;
a[29][2]=302933962;
a[29][3]=146881048;
a[29][4]=1293210;
a[29][5]=1299282;
a[29][6]=1305934;
a[29][7]=1444776;
a[29][8]=1394582;
a[29][9]=1406382;
a[29][10]=1424638;
a[29][11]=1476226;
a[29][12]=1288544;
a[29][13]=1181078;
a[29][14]=1339638;
a[29][15]=1320828;
a[29][16]=1429310;
a[29][17]=1417880;
a[29][18]=1404154;
a[29][19]=1295970;
a[29][20]=1351344;
a[29][21]=1203706;
a[29][22]=1429282;
a[29][23]=2110382;
a[29][24]=1731108;
a[29][25]=1206338;
a[29][26]=1238042;
a[29][27]=1751446;
a[29][28]=1357450;
a[29][29]=8422068;
a[29][30]=2768;
a[30][0]=958036;
a[30][1]=2546;
a[30][2]=1038622;
a[30][3]=3524;
a[30][4]=5542;
a[30][5]=3012;
a[30][6]=4120;
a[30][7]=3550;
a[30][8]=2594;
a[30][9]=3880;
a[30][10]=2796;
a[30][11]=3606;
a[30][12]=3454;
a[30][13]=4336;
a[30][14]=2792;
a[30][15]=3156;
a[30][16]=3214;
a[30][17]=5944;
a[30][18]=3938;
a[30][19]=3588;
a[30][20]=4834;
a[30][21]=4494;
a[30][22]=2904;
a[30][23]=2908;
a[30][24]=7948;
a[30][25]=3676;
a[30][26]=4842;
a[30][27]=6758;
a[30][28]=3502;
a[30][29]=2768;
a[30][30]=15000;
    //a
    for (long long i=0;i<=30;i++)
    for (long long j=0;j<=30;j++)
    {
        sum[i][j]=a[i][j];
        if (i) sum[i][j]+=sum[i-1][j];
        if (j) sum[i][j]+=sum[i][j-1];
        if ((i)&&(j)) sum[i][j]-=sum[i-1][j-1];
    }
    long long t;scanf("%I64d",&t);
    while (t--)
    {
        long long n,m;
        scanf("%I64d%I64d",&n,&m);
        long long ans=0;
        if ((n/500>=1)&&(m/500>=1)) ans=sum[n/500-1][m/500-1];
        for (long long i=1;i<=n;i++)
        for (long long j=max(1ll,m/500*500);j<=m;j++)
            ans+=gcd(i&j,i|j);
        for (long long i=max(1ll,n/500*500);i<=n;i++)
        for (long long j=1;j<=m;j++)
            ans+=gcd(i&j,i|j);
        for (long long i=max(1ll,n/500*500);i<=n;i++)
        for (long long j=max(1ll,m/500*500);j<=m;j++)
            ans-=gcd(i&j,i|j);
        printf("%I64d\n",ans);
    }
}