#include <iostream>
#include <cstdio>
#include <cstring>
#include <bitset>
#include <random>
#include <chrono>
#include <algorithm>
using namespace std;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
int t,sub_id,n,m,N,M;
int book[3005][3005];
int tot,sta[1000005][2];
void add(int x,int y){
	if (x==y||book[x][y]==1||book[y][x]==1)return;
	++tot;
	sta[tot][0]=x,sta[tot][1]=y;
	book[x][y]=book[y][x]=1;
	return;
}
void out(){
	printf("%d %d\n",N,tot);
	for (int i=1;i<=tot;i++)printf("%d %d\n",sta[i][0],sta[i][1]);
	return;
}
bool prime(int x){
	if (x<2)return 0;
	for (int i=2;i*i<=x;i++)
		if (x%i==0)return 0;
	return 1;
}
pair<int,int> e[1000005];
int ans_6[5335]={30200,39111,24980,16158,55809,51897,49977,46245,35983,18499,14491,42384,17120,10429,24596,5138,13284,21332,20303,40488,23128,481,37290,46489,18023,8320,1213,8218,23942,48224,28135,57202,41627,45467,8378,52424,53690,27078,11012,6943,44446,12351,14030,685,34744,5821,42147,17903,9235,1913,3168,18655,11525,39851,48934,49602,32850,21634,13960,50910,2115,42243,27898,2988,55477,36689,18047,44656,40921,48970,38919,52325,43087,23101,56565,45760,6900,56682,33304,46375,56229,9764,57426,2469,9081,50509,31068,47225,25092,43382,4161,33959,12687,27363,19789,3735,29594,54471,40245,8388,713,21339,25391,47458,17966,56189,20796,45172,15763,15864,44467,56312,3867,24937,25200,46971,6808,16247,26954,31573,30671,38420,50474,45557,54834,25830,14861,18390,35435,28193,45950,55514,23991,17975,48183,3506,32075,8539,26293,25605,50482,43106,55871,26404,23384,46269,32727,54523,25325,56795,31933,40988,46632,36556,26027,6573,5139,30237,57489,7968,1631,2784,12480,40175,6834,20457,21080,46067,9218,50939,4467,39094,47782,26411,55086,53605,57392,31188,47635,41262,57369,41719,21933,12572,44940,33925,20297,31419,41720,9175,35316,24668,33787,13791,29202,26364,52716,48066,38361,58073,17138,3038,3903,33668,48523,56329,34181,22824,26810,31314,9561,23223,32718,12101,3137,34749,9171,27547,44032,50328,47028,11112,22480,708,39040,12931,35915,22626,45943,11210,21825,9347,50298,37843,47265,55658,34504,57185,1883,27593,12133,53400,20178,46645,5886,25566,27950,16399,7896,37358,16725,12135,11976,40887,20755,28324,30910,54366,39730,3463,57896,36270,4914,30305,36575,9476,37970,6273,19109,14420,34183,46363,19439,43597,25955,19670,50596,1433,16707,44893,49856,37862,37381,1387,17652,2085,34268,1293,6537,20916,57749,16172,51546,17245,22192,49622,20670,29517,1390,14305,29073,46344,29627,7267,29828,18151,26279,53114,3112,57936,29178,16612,14062,32456,18988,35492,42348,54812,37293,57188,57191,22546,8986,33501,44046,56442,50411,21497,14670,17703,57644,34906,27285,45415,23970,13672,51842,12542,14326,54348,4589,42931,244,21105,38838,15992,1661,39523,35890,12137,50912,623,53369,56498,12699,43200,57297,7549,8603,21148,34892,30153,43470,17488,28218,40749,20456,50151,26489,21891,671,19782,24059,47797,34672,12260,17836,27831,38927,21044,46052,30595,1808,55474,47521,57776,47382,6312,21293,48500,9852,56951,21469,25244,35347,22498,23044,33140,35270,28975,12925,34303,34105,40416,48658,53411,12624,4578,54603,2249,5309,17750,50975,49707,30534,55324,32424,20648,32368,11190,36816,15383,42287,26627,13822,56057,1343,36147,30262,36174,35165,57566,8373,18991,26131,27661,46662,26106,35706,16334,20006,48776,18634,40742,40213,7165,29162,38777,49535,46202,30378,55468,49605,13107,12760,13412,50882,1898,32120,54608,48128,25485,37613,9747,2903,55308,46474,12107,4604,42329,15386,37881,49922,43464,21741,32329,26970,41429,28767,30941,14924,34555,19525,9949,56104,25573,5605,56224,29258,17972,42239,36380,55675,52339,7066,12443,15782,32490,26724,40602,29875,12381,9821,54062,48711,51436,3106,696,56373,23137,56965,39203,57756,4780,42415,47227,48920,37168,32757,58058,57071,22843,15784,41192,50404,30601,16027,26283,56673,44608,17604,29387,11431,18016,33180,49874,30903,22536,54329,29590,41421,33564,8677,17879,30162,30907,28835,12210,9947,47232,4328,51194,17234,46692,13450,22511,32153,51469,42809,10960,41363,55883,50953,24306,26295,3971,57103,8047,11628,32011,43558,28656,57666,4910,32390,48302,20858,2930,446,31036,27109,11813,37138,52358,57537,7110,38311,30415,2810,650,48397,1516,13964,39821,30621,11090,15866,9069,53125,27870,13507,40802,41818,53262,10761,23130,3198,39661,32993,45659,48545,35320,6235,22489,42133,41179,2791,40969,22849,33624,12311,47171,33954,25189,17449,17406,49059,50098,18717,35819,37059,1616,40772,6914,33758,52183,37987,24609,25906,15065,36834,41448,51304,3089,32076,22024,38677,30334,27415,22940,44854,33065,22664,7149,38100,21723,53656,58275,25631,28304,41468,30157,1902,28298,21828,36934,31953,13374,24931,50629,40,36468,25183,23649,42358,11068,34993,7254,36664,52473,40535,49861,50457,51356,52470,37812,2705,46686,40665,1873,11427,11152,23440,55176,27297,36432,50219,49001,30201,45596,45099,29020,3218,33904,3141,58549,58388,34274,57466,51664,15449,28575,29877,18838,29609,42024,24731,18477,44543,12293,47675,43557,15720,6062,37621,23810,42181,49539,24839,17624,55594,32930,24425,1225,17351,38417,11315,48,48908,49193,26703,57576,28954,32788,13163,5342,15722,20790,43128,53008,15284,27828,41902,31841,8505,19016,45003,12749,57446,49294,7329,39741,56898,53217,54514,52984,20214,38378,47765,35072,24398,2560,47720,1175,44741,6008,3020,16032,24654,8472,50653,34962,52291,3496,43014,29869,55970,19487,51271,51787,294,52446,32683,53346,12337,28847,43500,54281,32733,54031,48638,24155,16038,53934,50252,35658,3310,37985,48942,12060,32959,16164,49521,26764,23929,40687,41612,35123,25184,50793,38547,49048,56083,19689,58014,20958,8936,13173,22836,14018,33420,43943,37431,18847,10799,16577,7901,26420,43577,49499,684,9613,27925,56542,31287,36428,32480,28030,15061,21624,54960,20045,23969,36345,7915,16559,9161,24245,38852,18349,30411,37981,55546,15132,21840,8894,18942,1837,43720,53600,19937,16807,5305,54414,6081,3034,32598,19317,29275,38382,5565,46734,23587,22983,58117,55478,21932,11839,12115,28334,51285,46335,25589,40869,37383,31194,52989,35152,14972,28587,52296,41855,5185,20262,20598,34687,49904,25384,30617,40412,13854,13442,33154,18929,46604,47343,5507,9453,40940,39954,33621,3139,32165,44051,32039,19739,15329,15624,34224,26061,1639,29480,36706,50085,45759,52531,47568,37818,35035,37959,50742,554,52707,6375,34271,35139,28473,43181,47814,30013,40712,29663,36691,50461,44550,57717,36684,13845,56511,20524,41154,1454,11212,36819,39620,39419,42164,1489,665,28143,34323,6601,57521,17444,24657,28879,15101,53828,5378,18812,37016,57049,38137,24679,24842,37622,17833,19532,57588,56828,17623,2536,29183,6153,34786,32806,44288,4524,45550,10107,11006,43212,39548,13622,46230,10925,41157,17251,53594,45201,19356,6795,16470,7773,50556,1311,53580,25658,26678,38935,54188,7582,50076,56995,20062,14800,18635,43604,22371,37332,30870,27841,21937,25103,23759,23628,18338,2619,2539,1446,24734,4149,41943,5602,47619,57178,19399,44632,10517,14291,33464,11033,56423,20153,28814,22157,2036,40696,19075,23050,36526,39516,21789,27819,43560,32872,49338,50982,17048,31901,8546,13090,56821,11341,13270,32548,53779,54,11788,50932,38344,55202,44570,7475,23115,52687,3327,48262,39308,53155,35018,37623,7694,16443,24412,45972,55851,17753,55395,51307,3754,46051,43651,41335,23779,48627,10439,17810,14704,48683,12180,52054,29984,26888,4288,3196,4952,26480,45737,36430,36010,21054,21703,17402,3716,47467,28869,1410,29844,38172,21278,25679,33573,58564,15143,28456,11914,13698,54944,19276,45937,33927,58467,30971,18461,22722,44107,13192,53944,58248,43440,37725,51691,26539,16978,23557,47437,34713,10594,18825,22772,50918,52132,54098,1846,34722,27982,6926,17264,24516,15105,19228,3863,38490,26099,35992,50665,41916,24724,43428,40955,28338,6607,57871,4988,32450,37015,14822,4645,27191,14674,25856,47096,50349,29437,51877,55173,10849,3784,19285,56488,34362,34679,6181,49149,58352,20946,41258,18389,5641,848,50452,15560,30377,1260,56584,16895,41678,42989,20604,18029,16098,56869,26977,32907,38578,46267,7921,6978,3590,54083,36248,20383,14027,173,28421,55300,27860,52988,49720,6562,18260,41878,46723,30017,37078,52908,15162,1281,8074,20028,19376,49815,6234,30492,42815,43192,33878,13611,19664,56807,51353,35499,30572,40174,16909,39017,36794,13532,15617,11543,9340,7232,21805,52443,19046,12498,11366,20583,14715,6810,26669,48163,8759,42460,32475,50577,23791,44557,32331,46959,9954,28702,20689,18791,29725,26572,9713,43631,23689,14455,51001,17864,43975,27608,56002,20121,52193,17621,13074,3203,33658,28629,58165,21265,26007,67,47453,52205,51577,53640,34669,45051,37655,37615,19009,19056,32923,31199,48695,54319,5363,33268,30187,36593,11820,49934,36728,6992,57788,54359,56186,14099,5700,22115,31579,9297,19216,1047,37167,13165,14702,40925,46476,21392,54036,1763,40605,10757,14197,48827,27773,20488,38009,21038,28393,38174,1328,27089,34365,24509,5059,42182,734,31724,15669,26620,42421,29586,48494,57597,10530,656,25867,54542,35353,32758,14672,126,35421,49751,38926,26227,29921,16727,39345,20845,32271,51057,22670,40106,24531,33562,30603,42895,49836,14521,7578,55251,27909,12789,2909,46018,46620,35812,37353,47646,15395,32293,14754,26177,51570,36465,7732,22963,38535,23549,54692,20908,27104,14419,56848,30787,639,19727,53801,16157,48259,38111,46174,34895,12538,33290,46493,24237,589,4192,35912,47464,14650,43718,30066,8946,31304,4187,17139,9290,28749,36511,13315,39549,53982,5853,35192,9065,9585,34191,33302,13732,53334,49008,42649,13352,1419,41961,56308,33503,24088,25914,23581,38793,13358,58586,6787,46671,35860,39829,56156,48258,15976,9910,55957,53742,30341,44930,55479,37947,40144,46983,42005,6940,25410,19846,4939,37753,529,15603,34646,1967,15623,11454,27488,10568,53882,24814,54092,23756,31691,16030,24880,1640,29866,4666,54255,32160,8157,51265,21296,3080,25546,23401,26786,30103,4013,25247,35767,46709,52250,2474,48960,25346,28907,1333,33339,50394,881,9208,16645,58231,43156,4171,43346,8823,33284,40597,10519,41681,22831,28436,32327,57757,43632,27995,54505,4699,40935,32310,9929,17289,54908,54537,26077,1252,46136,18898,40114,44581,15425,40821,37905,19100,54984,1032,3844,32789,47828,40754,48266,35710,37077,9512,14595,19967,18965,2818,15949,38545,22206,788,42845,31229,21093,35376,57195,7026,2548,41144,48981,16290,46433,30037,35102,39575,19939,1222,7739,36424,18259,14882,24821,53289,4203,23898,5420,49025,43653,3775,46420,25394,3562,41544,11409,22572,56420,20064,54722,18643,34029,45628,41024,7170,7641,34831,18966,34862,8922,23603,56852,44753,41802,10918,4314,53680,58651,2519,56390,30694,4967,3627,40354,37870,51219,5587,5467,36238,36224,53084,52820,32482,30003,35181,13082,1554,21951,45965,21095,49888,47898,29108,32338,1123,4492,31406,25991,22482,9753,8412,13778,58554,48802,11233,34818,30395,2195,33601,18163,20934,20337,27318,14390,24970,34233,17338,46398,48992,7730,33197,22922,33468,17416,53295,11879,970,51894,26691,6899,24833,38394,1182,31506,54914,1018,26268,40489,16266,49737,50251,2978,43729,18359,53517,25548,10081,10260,17697,12373,46813,41736,7922,32612,29626,19258,42126,47913,35951,9277,11457,8535,21730,45723,49655,47222,2849,17150,23574,45834,54882,45045,16001,16502,6987,28299,45077,57341,43554,43547,14847,31335,55685,1425,54800,48664,26252,33517,54926,9906,29562,52448,10485,12089,44786,48581,9309,33328,18253,45778,16518,1669,44516,17587,13176,13350,2020,1220,7051,5679,31960,14503,1622,49117,52158,49715,40208,56388,11713,2526,9796,53899,41202,44983,9895,43623,1411,17368,17408,44341,38575,19294,45011,19132,37288,12541,32219,34250,54943,58307,25850,2985,40811,27023,22994,52513,49830,18545,19953,36069,31416,22372,5972,53082,37826,42359,15342,55375,53490,39164,19035,56334,10683,55785,51803,42588,18147,39737,24561,53518,10493,53178,52455,3852,27065,46657,4172,1851,48206,45565,45055,45337,34563,43591,17011,36397,18080,42289,43860,22467,37892,58249,27565,30018,40863,28072,29344,47307,31885,14303,42643,23369,18570,46546,47558,8876,53277,38165,37650,13868,19241,56391,25625,11665,28525,22691,37406,12857,17842,20122,28122,13614,2163,46167,16207,28808,6816,288,23830,38152,38281,3489,30553,57082,55015,28024,5032,53856,10082,8052,52441,21466,45654,39815,13114,20396,32526,56313,43448,9770,17929,24324,21575,20850,33591,31207,46402,38556,28197,22606,46045,54594,43829,15822,51659,15794,57622,3432,27701,10258,39526,53133,52185,3604,30932,16655,41118,5033,13462,17393,43897,42378,46937,11122,33592,467,13551,6939,6820,9196,42023,34399,29863,43818,46326,34525,39341,39382,26065,13542,20664,39346,15724,6133,47974,3731,30368,38118,25727,40161,20283,8465,28748,10889,10936,16198,12163,22174,49200,30447,31020,5257,192,37435,44253,57504,27853,20143,28131,9632,14060,50733,40702,33912,38008,22672,52667,8058,28423,38479,49176,12512,20761,44635,35525,54444,4281,1349,3011,34941,55442,34774,16020,15905,21084,58464,39860,38553,42252,55623,28111,48582,8179,38928,13309,13370,8117,52930,8772,7644,56299,9888,20150,41072,5286,48613,14037,39045,50526,11807,25025,29050,4284,30465,55207,11702,46929,22303,57998,45257,20477,20744,29158,48096,53768,30183,55985,50262,43479,39165,47590,38981,15385,43046,3178,19402,10188,47064,42208,56687,12638,11445,17727,49489,23333,5017,23387,48446,16272,53815,49006,50422,34974,21230,8176,33588,39411,54193,19341,47030,53454,42670,19023,13875,48401,52872,7218,6512,1474,39911,28775,26117,56054,49462,19941,56710,37642,31182,6725,12017,55591,37466,52048,36190,48288,8768,46733,41111,18340,51456,18691,54055,30625,59,38796,45182,44910,44976,52506,12022,4531,19510,28120,39236,40771,54503,7511,21836,49259,24348,21569,11585,21367,15588,23947,24247,13833,12917,15274,10425,51826,26971,34983,9911,7530,16413,5070,2447,57127,20095,29733,6695,19478,37535,47435,15998,45731,5314,57239,28020,3083,6721,9349,8615,14257,3595,57692,38360,3059,31659,47484,11944,53176,55763,43103,47750,54191,51995,18088,52926,21695,8142,13658,22507,38853,4769,15316,48767,3887,25294,41240,30160,4944,1542,8156,13060,2484,29746,38374,13153,39403,50202,53482,5125,45032,38640,39006,29082,55404,49699,50786,9125,25257,19474,18664,30719,33253,45189,6368,55255,21405,40968,37397,41004,45857,10583,24126,16825,26863,38342,1440,17618,49434,26149,11913,7995,39286,52963,41927,51964,41994,40052,39557,2734,30102,12151,49204,5993,47727,3206,25480,7771,49109,57153,52599,34413,26313,46116,39609,4963,20596,26619,49754,9725,13426,31087,30616,24511,18465,11666,8893,35345,8770,57960,45321,8717,52152,58601,54867,21496,25366,28776,12317,45681,6383,41071,12442,6440,14256,3065,16265,187,27294,21168,18657,49777,39498,9778,9383,9430,16561,13094,55160,47829,40910,36402,6971,56522,49365,40051,22035,4153,42337,14556,38908,15344,1827,16615,15223,26555,14711,40748,47253,29660,26428,53536,41524,7465,41569,557,30049,58016,51535,43178,14714,5943,19775,21110,48948,10746,54932,41477,47305,58540,35916,14976,12607,40758,49379,16763,12611,10943,47477,30876,1158,41253,42754,44728,7595,6518,7728,3061,8750,9749,3332,4633,21992,33641,15696,5442,57377,35039,51785,32648,5566,17149,19090,5144,31750,48388,5414,53122,31630,8393,11051,51825,16330,3958,45314,45470,18365,53984,30009,9436,27190,47694,614,24379,23575,29432,30396,29087,15779,57667,8016,10528,19629,6457,16487,2625,13449,8639,11098,31469,48332,10975,49578,32244,677,43157,34209,19859,28076,42134,23091,25165,39126,28146,45376,54813,8600,23226,9490,9096,30640,39571,48400,41530,28822,2242,41385,19994,35162,56791,33014,7118,48467,18796,22987,46401,710,49722,57421,52140,30354,5648,7057,22867,33552,52420,5871,53663,36758,51240,17325,5607,31925,57442,46712,10375,28765,16119,21244,3921,19235,17640,8348,18884,55297,7478,2693,55302,51103,55572,16770,52502,2395,20936,50060,18568,40523,21,33811,50387,35865,55580,46625,27324,51414,27313,28793,36032,25179,57619,5802,43236,46211,47830,49350,40652,29548,15043,26439,1993,35770,36098,51442,16644,41743,47321,25175,37389,7416,51986,29881,52912,9055,14540,46549,17492,17617,47170,38652,55800,21420,10521,29773,35080,43681,20197,45232,37448,3134,26692,21389,47082,15320,58469,54433,21702,31686,56986,46800,53162,32171,4875,48010,49819,36033,30686,3911,27802,22972,8594,47971,45464,48161,24513,1033,44281,53827,15768,42705,8000,52286,11043,20463,47409,19079,49975,39289,6613,41637,45877,6706,7311,16925,22374,32695,31834,43004,49595,31930,51262,22402,10405,27650,10767,57804,5944,19128,37935,11063,19479,18539,50335,46156,28051,35621,23650,50230,2037,3702,33974,54671,44934,20815,37069,3543,22876,42626,20296,46967,34969,9806,40581,44424,32311,1461,14328,6954,6874,57703,57977,12470,38322,52762,9550,57410,43267,6600,10565,46451,42994,9393,2724,26158,54409,20279,5852,941,10402,17202,3236,30044,34684,116,24530,40197,29399,42025,5038,3628,37162,21864,31813,31354,47824,16557,46055,36986,43113,50711,15330,17403,3086,42818,33703,15021,51050,57956,37113,7006,32371,31682,57577,41189,4558,11668,31420,55022,1056,7191,8032,18853,40203,45407,43288,6362,53372,53174,36014,13221,40256,56228,24433,51772,3660,53466,988,56135,8311,30400,3989,53207,35,1020,33883,15694,29806,1530,10608,8194,14871,17053,39229,35876,45805,34201,8242,44367,58339,46483,28742,18712,8195,46783,57286,4619,36512,4267,3892,23589,21441,1179,49337,36066,44171,14403,29512,44254,36786,38597,9750,41051,34432,17957,36889,16821,23370,41159,14475,27919,52737,13043,3124,26202,5949,41726,47786,30299,44495,2918,36719,49461,40457,40740,32288,45374,52143,25904,16,36837,32561,24816,35995,20398,58431,13348,47031,31766,40711,7892,47896,12846,43754,18596,40237,17188,33800,5231,46392,51201,30696,30758,29219,6908,45167,36528,35632,21238,1832,47936,56686,9706,42308,21429,40233,53654,48356,25456,51153,34707,17024,30382,846,11684,38598,39687,27690,24684,9329,51759,17868,887,21567,15614,6281,22826,31213,57279,37872,438,34776,31584,2614,2203,19778,54697,7199,57657,10750,13559,34266,39574,3980,53397,21905,25222,53417,37237,26400,57907,43211,40683,10228,20843,47799,35208,35540,22862,359,47807,42456,56356,47047,39870,895,51251,5136,30344,4134,42773,42988,11126,34994,47510,8926,54253,30110,6246,58640,36806,817,30329,24036,37327,26509,51586,43242,27268,1107,41798,28964,23560,53303,24337,43898,36810,16984,16332,57959,11133,47775,6743,36126,16433,39218,53803,23166,106,24705,46831,17726,33285,35790,14474,2263,35106,15650,11932,1904,4820,44953,7780,42879,19013,36838,18730,48027,574,28909,12136,10832,11661,15415,51298,55995,48605,14482,7573,51020,14863,36415,15378,44752,7139,16270,34286,50994,32996,43348,7598,29139,46656,25979,29980,22491,6462,36012,10415,20366,29316,48268,31443,26641,43336,28269,28167,47524,12800,53928,17214,1811,41834,38073,36849,39786,56800,47552,43906,47544,29323,10379,35286,30242,27903,37249,13219,52163,15042,31595,14546,12515,48074,27579,42846,8490,12313,42608,39254,22996,2087,43791,5847,1728,31741,7369,23526,17422,21736,50376,48919,4137,26144,21276,34883,27305,41387,30809,27838,2431,15571,47363,38144,52512,7600,25239,17885,45653,6272,174,52520,48744,37710,44682,21839,31172,39481,57306,3637,21256,29396,25255,23814,29665,27284,16973,31441,50142,34427,24961,28173,5295,24267,47681,52452,44665,6484,55091,32074,46108,46527,4447,34747,15948,50669,3799,11377,51874,28266,43833,50562,11993,24519,51966,10747,20365,44840,42681,12419,28854,43081,27985,55283,30425,30346,36276,9047,39213,5267,45773,12489,15597,24754,26817,38691,46780,3182,891,34481,40366,23945,35022,4567,36303,52262,10074,29684,400,13725,38107,25187,44271,53025,2076,21844,28665,17564,58246,13786,56624,50898,58244,49246,14171,42921,29058,6786,180,24205,25227,26882,8929,44052,1834,6860,7241,47538,21948,2319,2225,31621,41087,32008,43822,24343,32024,55558,5755,56597,50122,52166,45963,10031,8050,29658,26005,11322,30713,58048,57918,6937,14815,29251,22000,49099,31086,14869,44721,312,30587,17671,11818,2380,58629,57362,39718,2941,10250,36617,30227,22458,14651,14569,4311,50263,45349,32334,8340,42484,28968,12269,23846,57731,57851,38834,4151,20716,20299,17683,7682,35222,32184,14577,13586,56950,19004,51178,51594,46905,36251,333,28564,26660,39324,53551,53246,815,28520,18347,26449,30659,14445,27910,45043,13770,35446,38343,23232,56737,54440,9135,41689,58334,32867,23069,22786,18118,45583,17715,54094,24045,56413,20363,26844,6076,2758,34812,26949,6620,24246,12208,18886,6311,10880,25851,38130,31812,29347,19155,18051,34573,42074,12828,51358,2262,17942,26720,53287,12914,32804,35740,21281,43823,44700,50425,54573,40626,53105,15689,42591,16103,32264,47326,56792,55336,29566,45754,3610,5912,23222,40097,55630,12214,16439,52422,42923,56874,32019,27951,46868,30660,12967,18405,26170,40688,40563,50229,20428,51600,6409,33182,40521,33940,55780,24374,17782,56955,34691,40682,37285,2349,38925,52329,24451,57312,24891,26686,6887,3821,51430,38676,7469,17563,18402,51801,8844,40085,33334,53704,55414,1386,3257,25948,22172,21170,53062,10220,402,26142,17034,7746,38228,48792,5690,28997,57539,11018,5983,39850,37478,14264,26331,6557,19952,15528,3372,34414,52691,40512,23412,32179,57294,34950,53505,19997,26791,23735,8508,57052,28245,33815,38276,48369,4613,47785,37806,57638,38582,25001,10216,47387,37857,27243,50245,26030,37836,1823,13225,44065,18651,21595,24453,37635,40870,53457,27538,23815,52617,41018,17040,58024,52782,23256,11548,2551,4764,7397,47827,13689,34163,4407,6002,5692,53462,2992,25144,2710,16280,24069,7399,34625,46025,27631,16749,44213,25881,23639,25178,16099,31679,4811,4073,22547,7532,34849,28289,7657,19584,15428,44292,55391,722,7381,28617,26416,45636,11413,29602,23602,31776,57280,5199,4552,8879,31833,28012,36026,7850,51095,2907,13193,39746,32200,36587,2922,33527,18101,19170,35268,57087,34497,37432,42970,55717,24330,25684,16483,23607,51514,8483,19150,33660,33499,371,35772,21476,29364,39318,11572,6050,4453,5480,48326,25036,7033,1168,47722,24685,20605,52633,25654,10923,2805,8060,5781,8290,1741,8550,33109,17033,52272,27857,8877,54857,44330,14846,47196,41978,35999,15022,53245,2821,35696,9044,48646,33272,13982,4357,32266,3013,24973,39025,17207,4798,55034,6551,4556,32050,54240,43633,38031,27055,42312,7122,37258,15903,58359,50239,17191,41248,52648,26909,7664,33369,24858,18974,26807,33484,9299,27691,63,22414,33478,27168,45279,22211,37033,14343,21269,24048,49133,6347,13184,36917,16286,27135,19076,43586,25490,50041,40046,57542,15217,31286,36645,39342,54029,40126,49624,16206,29190,2807,51949,18896,50905,57862,36792,8698,19882,10575,9948,32599,32838,12855,52866,56939,51000,54507,34642,40576,5104,22801,50741,14433,13987,37606,36210,24480,19515,34576,36229,47589,34914,10435,52336,9097,51937,11412,16505,2653,48198,12791,44120,22202,9254,45536,57004,54701,29607,53735,45461,15268,2268,21057,29525,13208,45810,23777,29136,36882,35593,15313,36872,2674,29511,21772,54730,11554,11875,25230,27220,38004,33443,27577,56641,16064,54385,40260,21360,40713,32614,57183,31403,38474,16755,21209,10416,12814,25545,5538,9717,10824,47925,13200,27740,43262,995,687,35304,33510,27430,25908,22756,22217,44377,9046,2788,23690,33400,15351,380,58539,30865,35591,38552,20059,54739,51086,31090,39777,26371,53432,11626,56482,6754,46160,46086,55048,31657,38970,26937,46993,22051,45698,8200,49106,6862,14463,44019,44555,19206,43507,43472,36326,39582,18642,50161,14778,558,23715,38093,26738,8041,50604,8650,22092,43761,23356,17780,10012,322,20489,5389,38533,6957,18134,24428,56563,49502,8110,13979,10338,40244,55812,10390,14664,16166,22811,21655,11351,49411,44097,20549,34821,23922,38054,27520,10861,40454,32463,30999,46231,36222,18864,38809,52027,486,19152,2434,20444,27638,28506,55548,38246,50470,37983,49627,53307,42729,2629,12612,46442,19400,52357,39921,31310,18799,36120,46434,30426,7685,13096,57092,43810,18765,976,11518,18250,32027,19740,22065,56623,30326,21887,21945,3384,30873,248,49261,37942,35874,21583,10302,34454,51687,44822,5589,57081,53361,14312,32862,23990,46900,28899,46665,45970,38155,30750,9332,6352,55484,54807,9518,10126,42305,43052,13065,30536,49161,22874,18464,42827,10718,54645,5635,22239,44265,58310,28341,24377,52656,23178,49366,34718,6175,6065,34051,42575,29377,49962,45171,57600,3840,28331,29670,30821,19812,40622,6506,40456,3788,47124,28824,5209,42141,36289,16474,26639,42688,4420,35612,43054,47502,50545,38690,54200,14437,34322,17948,15175,34231,58377,44929,55867,39277,11843,26086,16183,30911,31433,44414,18535,46056,14157,28198,54752,13641,27374,37300,40994,13057,1059,36310,979,2288,12984,58028,57360,16730,26514,31430,39019,35358,48782,17665,34275,45689,46879,27750,35863,25087,23259,55152,46338,34380,52812,39469,18326,40950,28455,11070,45482,14879,7808,45637,18507,40545,47611,3070,28037,42390,18762,18414,55836,33384,18217,38513,32415,13568,3170,30924,13191,15475,56389,52852,8855,25885,15282,8467,22060,19703,49458,7542,58611,44429,16702,647,54596,8856,41172,54621,33330,28536,28049,36332,35671,797,58374,5588,53050,16177,44562,31939,3714,25928,4371,23608,48639,31040,15380,23993,43896,6454,49532,15194,17513,5628,15024,21437,13597,12904,55575,11262,33069,10143,26289,7070,17187,55491,7133,53559,7969,36290,24029,32649,47084,30507,20687,5482,11620,54297,45882,7592,4700,18606,22194,53146,14213,30369,10403,48779,51198,54562,36108,47257,3557,7502,15601,55626,15939,19597,54791,23365,29420,54799,54139,354,3393,44170,47032,5989,28416,56169,6476,1742,21239,4518,2451,8303,40424,28597,19443,21833,25451,45650,37500,30935,51683,33507,40061,42489,13878,43618,49062,22185,6049,37268,886,26814,27501,10215,38747,43677,14169,16455,20636,12999,19657,19365,35765,48889,4776,8745,49142,23609,2279,20110,15816,48651,53644,26502,6942,28982,52313,41731,30863,8661,4839,13143,9240,9067,5300,18226,53619,24917,44396,1795,9973,25610,5217,973,42093,49788,13349,52862,31371,6116,10867,40790,37770,51309,13891,57762,48490,32229,634,39606,52047,11470,34031,31193,43059,32106,45807,5687,41041,19861,25196,49657,22104,26234,17117,42016,12905,4584,26744,54700,40008,16422,24665,2789,32099,13883,32874,3040,26664,25220,6450,37151,29264,42642,33931,37075,45503,38104,6139,44654,26730,33221,4454,2514,4865,28688,51316,22765,15470,17313,7604,25676,4920,52690,29833,13862,37032,48461,51545,42366,56861,25216,45506,39394,49893,765,25076,29700,12424,50483,24900,9211,19519,28902,23211,16646,43992,25763,6140,40291,49172,9730,31880,42345,40021,4080,5219,37559,25555,1472,1555,24137,15119,36639,52899,3485,7174,22728,50614,35542,25699,18580,44217,4581,26706,34429,21102,48834,31738,19232,32066,10862,38325,56705,19558,2915,33200,11502,12518,24487,56868,10172,56144,41980,19673,530,22752,46852,8796,53499,10327,44069,32203,47562,51738,31074,7406,16705,44856,31831,55120,14024,46470,12696,53516,23836,44798,23411,17960,29772,30992,55715,23262,53802,37195,12551,42520,45381,33725,32979,7539,48406,17544,24550,56337,50768,46170,56638,33003,14825,9943,5926,1978,5967,37589,13754,44148,14641,48823,43015,44965,39539,7212,47365,54161,48741,51495,960,6659,7225,18926,46163,17194,34513,30877,25892,29633,27607,35753,49524,8408,22938,32081,11096,25157,22592,5855,5649,51579,41255,47144,26645,40671,54889,22809,47761,30967,58064,21692,2889,40466,34935,39607,41438,20458,10502,13659,512,8059,43606,25032,4880,18280,38711,4303,16563,21070,58289,24918,12862,6135,170,45044,56964,5410,28786,55060,6633,23221,31482,4247,54684,23071,42476,39156,49775,13489,41508,42395,10903,43977,19804,57564,34780,43047,53572,2254,9930,18104,26948,19707,5796,11589,37526,55409,22259,53437,46011,20969,6179,28833,40441,47439,19141,45615,4343,39827,47283,56978,56174,51036,11526,15802,51476,1184,9381,5515,49346,13366,23833,46731,56935,16728,46949,29224,14805,18866,22395,14365,29757,13949,29119,2531,53367,25707,28695,23937,36548,28061,21576,13924,37407,9129,24151,35645,55110,43926,12225,54445,11391,19964,40064,20175,38685,5003,16849,32477,23842,6546,7140,57888,1231,3456,23977,43307,47071,22171,35521,1991,9970,41428,51342,15357,24166,47658,55694,9413,11437,25518,25146,44484,22863,4924,43354,44751,45164,14396,17362,46453,49955,11173,38206,3501,693,42604,12764,19824,7255,33305,31672,2533,24535,27502,26341,9180,17332,56547,39033,30578,56966,29135,2277,23436,25982,18010,42816,48109,39108,35250,24909,34989,25249,7866,18661,1041,57305,13702,43466,15188,13916,35096,15407,2848,32641,27129,33058,53725,36658,51058,45732,9912,5867,31549,8667,31542,11959,45584,41642,56395,36104,23442,1219,57815,32125,9222,29822,18017,15968,22233,39999,56872,15791,50855,12149,41691,34295,2744,32041,58112,37343,14359,15005,6671,39405,35005,34091,13514,54446,40584,29462,11799,47245,56731,33363,46168,1445,5906,26894,3457,19545,11587,56341,28707,37017,5196,45126,8137,34459,39424,35450,10277,38168,24846,31332,43010,11884,35114,16473,16062,44231,20627,33261,43768,15251,40892,1443,13115,33108,53210,4859,32515,25116,52359,43329,33098,9803,30575,29929,28915,17005,51023,33844,43701,11728,20038,10668,39309,57233,21817,13393,43991,22116,38340,53469,32498,54088,42020,2035,4139,8749,44196,10713,5247,28494,42686,33348,28646,25504,6566,26727,55052,49710,39521,1914,35423,54380,32686,36602,2286,51171,53968,34389,23017,39464,25907,15652,34136,42284,15654,3717,55689,45067,40487,54056,13972,25073,53975,6915,14946,46137,4163,23729,33771,44245,56920,51467,23584,57440,25378,7884,22208,22690,20533,21241,1923,49299,14427,32181,27437,14299,54373,51360,1351,27963,18252,55275,37498,54163,24007,27053,17163,47747,40674,8005,538,32422,48835,58062,19665,27491,48697,30063,22373,39484,17229,56996,12067,19741,20501,31499,27636,52554,8579,34134,7656,19675,8674,14222,55669,26393,36165,38402,33212,29766,7632,6080,10010,47653,11367,5732,35674,39483,45725,47771,54195,37036,55701,19461,19871,51940,23630,41917,55649,53581,22180,9494,52574,39145,53738,13986,37840,18181,22228,10801,24228,25717,28002,21127,18138,54568,19391,27382,53777,39359,20800,10542,13804,35564,37580,28182,39733,55495,19660,1698,43936,14272,42240,27506,12676,32647,30652,35054,14864,50392,13676,25837,39775,52670,18057,4771,24092,49084,42763,22554,18358,8371,23335,55852,41312,45535,54402,55168,8529,35834,2112,37444,8339,36867,24508,285,43737,44206,25781,4056,51361,50149,11948,52556,36941,34955,5509,48160,53321,10113,23668,42880,44227,34159,1434,21681,2063,41378,38116,31145,41526,10907,3215,9592,4384,43138,4529,3398,38632,50894,34972,23611,58152,55262,27657,45226,31658,43535,42458,32308,12526,51669,51138,17466,11715,260,45338,21777,21052,50815,13612,49951,34441,42706,28712,33177,40698,49625,42130,47065,43731,25535,8924,52688,7334,14772,33203,28091,39578,17896,5527,32017,3475,24396,18646,2442,40312,9793,11510,1397,295,32741,9951,47793,56587,46691,29986,12348,48679,7778,2097,51187,2045,54848,37676,55640,22854,45150,13421,2541,21442,11109,38977,47555,12310,11162,10674,5662,28469,42936,14518,22946,36269,46024,8300,11180,47926,46687,19887,12685,42361,42209,51022,25977,47710,45839,22166,53247,27543,50034,2074,37593,33448,56658,4361,36277,25293,8436,10932,48521,28323,29097,45899,52029,39331,34173,27548,20809,56606,21173,46162,29956,11363,4717,51969,52711,31810,44558,2188,41376,4475,11031,34057,776,44376,21109,31899,2929,48878,11204,43826,53428,7816,25822,42376,32448,23825,11,38955,45250,29522,48338,86,5818,3786,36306,7275,53664,3458,24875,21782,46765,15526,19275,40132,21289,14371,22075,7554,21140,22524,38842,43529,53280,50721,42872,10099,31033,31922,51700,24159,30665,7402,41746,28481,23054,15899,3404,18671,43806,51959,56127,27500,11746,50697,35227,16621,54922,14626,18107,53078,31465,26343,39937,27480,18291,22298,20415,48429,18049,49231,38461,33190,19786,34784,23717,17886,22249,5259,12736,56550,45634,25942,17511,52588,42748,40741,36775,11019,33750,1838,27228,1949,48452,384,43572,22455,23241,22329,28428,11931,38939,44435,28422,9967,38818,21803,44711,2327,14995,44372,57303,29800,14120,50051,21631,42398,383,4757,14080,41425,10507,51044,9087,38588,37106,235,27886,11731,49128,24172,25950,24622,14770,25523,28514,53398,53244,3348,54052,14810,7900,23511,40180,15377,29769,28689,11718,10478,16122,28697,16930,50307,9714,52079,34532,25317,27645,35053,58596,39806,29075,50350,33081,12679,45901,15463,57999,40706,54307,17459,25084,30998,49327,38334,47945,28567,8191,43924,284,5618,40370,3563,14105,30546,45095,28517,49676,839,35590,53342,31843,624,43989,48856,45228};
int main(){
	scanf("%d%d",&t,&sub_id);
	while(t--){
		scanf("%d%d",&n,&m);
		for (int i=1;i<=m;i++){
			int x,y;
			scanf("%d%d",&x,&y);
		}
		scanf("%d%d",&N,&M);
		tot=0;
		memset(book,0,sizeof(book));
		if (sub_id==1){
			for (int i=1;i<=N/2;i++)
				for (int j=N/2+1;j<=N;j++)
					add(i,j);
			out();
		}
		if (sub_id==2){
			for (int i=1;i<=N;i++)
				for (int j=i+1;j<=N;j++)
					if (i%(n-1)!=j%(n-1))add(i,j);
			out();
		}
		if (sub_id==3||sub_id==4||sub_id==5){
			int p=-1;
			for (int i=N;i>=1;i--)
				if (i*i<=N/2&&prime(i)){
					p=i;
					break;
				}
			int id=p*p;
			for (int i=0;i<p;i++)
				for (int d=0;d<p;d++){
					int s=++id;
					for (int j=0,t=i;j<p;j++,t=(t+d)%p)
						add(s,j*p+t+1);
				}
			out();
		}
		if (sub_id==6){
			int id_tot=0;
			for (int i=1;i<=N;i++)
				for (int j=i+1;j<=N;j++)
					e[++id_tot]=make_pair(i,j);
			for (int i=1;ans_6[i]!=0;i++)add(e[ans_6[i]].first,e[ans_6[i]].second);
			out();
		}
	}
	return 0;
}