#include<stdio.h>
#include<stdlib.h>
int main() {
    int num[]={4,6,8,9,10,18,40,44,46,48,49,60,64,66,68,69,80,81,84,86,88,90,94,96,99,100,108,180,400,404,406,408,440,444,446,448,460,464,466,468,469,480,484,486,488,490,494,496,600,604,606,608,609,640,644,646,648,649,660,664,666,668,669,680,684,686,688,690,694,696,699,800,801,804,806,808,810,818,840,844,846,848,860,864,866,868,880,884,886,888,900,906,909,940,946,949,960,964,966,969,990,996,999,1000,1008,1080,1800,4000,4004,4006,4008,4040,4044,4046,4048,4060,4064,4066,4068,4080,4084,4086,4088,4400,4404,4406,4408,4440,4444,4446,4448,4460,4464,4466,4468,4480,4484,4486,4488,4600,4604,4606,4608,4640,4644,4646,4648,4660,4664,4666,4668,4669,4680,4684,4686,4688,4690,4694,4696,4800,4804,4806,4808,4840,4844,4846,4848,4860,4864,4866,4868,4880,4884,4886,4888,4900,4906,4940,4946,4960,4964,4966,6000,6004,6006,6008,6009,6040,6044,6046,6048,6049,6060,6064,6066,6068,6069,6080,6084,6086,6088,6090,6094,6096,6099,6400,6404,6406,6408,6440,6444,6446,6448,6460,6464,6466,6468,6480,6484,6486,6488,6490,6494,6496,6600,6604,6606,6608,6609,6640,6644,6646,6648,6649,6660,6664,6666,6668,6669,6680,6684,6686,6688,6690,6694,6696,6699,6800,6804,6806,6808,6840,6844,6846,6848,6860,6864,6866,6868,6880,6884,6886,6888,6900,6906,6909,6940,6946,6960,6964,6966,6969,6990,6996,6999,8000,8001,8004,8006,8008,8010,8018,8040,8044,8046,8048,8060,8064,8066,8068,8080,8084,8086,8088,8100,8108,8180,8400,8404,8406,8408,8440,8444,8446,8448,8460,8464,8466,8468,8480,8484,8486,8488,8600,8604,8606,8608,8640,8644,8646,8648,8660,8664,8666,8668,8680,8684,8686,8688,8800,8804,8806,8808,8840,8844,8846,8848,8860,8864,8866,8868,8880,8884,8886,8888,9000,9006,9009,9060,9066,9069,9090,9096,9099,9400,9406,9460,9466,9490,9600,9606,9609,9640,9660,9664,9666,9669,9690,9696,9699,9900,9906,9909,9960,9966,9969,9990,9996,9999,10000,10008,10080,10800,18000,40000,40004,40006,40008,40040,40044,40046,40048,40060,40064,40066,40068,40080,40084,40086,40088,40400,40404,40406,40408,40440,40444,40446,40448,40460,40464,40466,40468,40480,40484,40486,40488,40600,40604,40606,40608,40640,40644,40646,40648,40660,40664,40666,40668,40680,40684,40686,40688,40800,40804,40806,40808,40840,40844,40846,40848,40860,40864,40866,40868,40880,40884,40886,40888,44000,44004,44006,44008,44040,44044,44046,44048,44060,44064,44066,44068,44080,44084,44086,44088,44400,44404,44406,44408,44440,44444,44446,44448,44460,44464,44466,44468,44480,44484,44486,44488,44600,44604,44606,44608,44640,44644,44646,44648,44660,44664,44666,44668,44680,44684,44686,44688,44800,44804,44806,44808,44840,44844,44846,44848,44860,44864,44866,44868,44880,44884,44886,44888,46000,46004,46006,46008,46040,46044,46046,46048,46060,46064,46066,46068,46080,46084,46086,46088,46400,46404,46406,46408,46440,46444,46446,46448,46460,46464,46466,46468,46480,46484,46486,46488,46600,46604,46606,46608,46640,46644,46646,46648,46660,46664,46666,46668,46669,46680,46684,46686,46688,46690,46694,46696,46800,46804,46806,46808,46840,46844,46846,46848,46860,46864,46866,46868,46880,46884,46886,46888,46900,46906,46940,46946,46960,46964,46966,48000,48004,48006,48008,48040,48044,48046,48048,48060,48064,48066,48068,48080,48084,48086,48088,48400,48404,48406,48408,48440,48444,48446,48448,48460,48464,48466,48468,48480,48484,48486,48488,48600,48604,48606,48608,48640,48644,48646,48648,48660,48664,48666,48668,48680,48684,48686,48688,48800,48804,48806,48808,48840,48844,48846,48848,48860,48864,48866,48868,48880,48884,48886,48888,49000,49006,49060,49066,49400,49406,49460,49466,49600,49606,49640,49660,49664,49666,60000,60004,60006,60008,60009,60040,60044,60046,60048,60049,60060,60064,60066,60068,60069,60080,60084,60086,60088,60090,60094,60096,60099,60400,60404,60406,60408,60440,60444,60446,60448,60460,60464,60466,60468,60480,60484,60486,60488,60490,60494,60496,60600,60604,60606,60608,60609,60640,60644,60646,60648,60660,60664,60666,60668,60669,60680,60684,60686,60688,60690,60694,60696,60699,60800,60804,60806,60808,60840,60844,60846,60848,60860,60864,60866,60868,60880,60884,60886,60888,60900,60906,60909,60940,60946,60960,60964,60966,60969,60990,60996,60999,64000,64004,64006,64008,64040,64044,64046,64048,64060,64064,64066,64068,64080,64084,64086,64088,64400,64404,64406,64408,64440,64444,64446,64448,64460,64464,64466,64468,64480,64484,64486,64488,64600,64604,64606,64608,64640,64644,64646,64648,64660,64664,64666,64668,64680,64684,64686,64688,64800,64804,64806,64808,64840,64844,64846,64848,64860,64864,64866,64868,64880,64884,64886,64888,64900,64906,64940,64946,64960,64964,64966,66000,66004,66006,66008,66009,66040,66044,66046,66048,66049,66060,66064,66066,66068,66069,66080,66084,66086,66088,66090,66094,66096,66099,66400,66404,66406,66408,66440,66444,66446,66448,66460,66464,66466,66468,66480,66484,66486,66488,66490,66494,66496,66600,66604,66606,66608,66609,66640,66644,66646,66648,66649,66660,66664,66666,66668,66669,66680,66684,66686,66688,66690,66694,66696,66699,66800,66804,66806,66808,66840,66844,66846,66848,66860,66864,66866,66868,66880,66884,66886,66888,66900,66906,66909,66940,66946,66960,66964,66966,66969,66990,66996,66999,68000,68004,68006,68008,68040,68044,68046,68048,68060,68064,68066,68068,68080,68084,68086,68088,68400,68404,68406,68408,68440,68444,68446,68448,68460,68464,68466,68468,68480,68484,68486,68488,68600,68604,68606,68608,68640,68644,68646,68648,68660,68664,68666,68668,68680,68684,68686,68688,68800,68804,68806,68808,68840,68844,68846,68848,68860,68864,68866,68868,68880,68884,68886,68888,69000,69006,69009,69060,69066,69069,69090,69096,69099,69400,69406,69460,69466,69600,69606,69609,69640,69660,69664,69666,69669,69690,69696,69699,69900,69906,69909,69960,69966,69969,69990,69996,69999,80000,80001,80004,80006,80008,80010,80018,80040,80044,80046,80048,80060,80064,80066,80068,80080,80084,80086,80088,80100,80108,80180,80400,80404,80406,80408,80440,80444,80446,80448,80460,80464,80466,80468,80480,80484,80486,80488,80600,80604,80606,80608,80640,80644,80646,80648,80660,80664,80666,80668,80680,80684,80686,80688,80800,80804,80806,80808,80840,80844,80846,80848,80860,80864,80866,80868,80880,80884,80886,80888,81000,81008,81080,81800,84000,84004,84006,84008,84040,84044,84046,84048,84060,84064,84066,84068,84080,84084,84086,84088,84400,84404,84406,84408,84440,84444,84446,84448,84460,84464,84466,84468,84480,84484,84486,84488,84600,84604,84606,84608,84640,84644,84646,84648,84660,84664,84666,84668,84680,84684,84686,84688,84800,84804,84806,84808,84840,84844,84846,84848,84860,84864,84866,84868,84880,84884,84886,84888,86000,86004,86006,86008,86040,86044,86046,86048,86060,86064,86066,86068,86080,86084,86086,86088,86400,86404,86406,86408,86440,86444,86446,86448,86460,86464,86466,86468,86480,86484,86486,86488,86600,86604,86606,86608,86640,86644,86646,86648,86660,86664,86666,86668,86680,86684,86686,86688,86800,86804,86806,86808,86840,86844,86846,86848,86860,86864,86866,86868,86880,86884,86886,86888,88000,88004,88006,88008,88040,88044,88046,88048,88060,88064,88066,88068,88080,88084,88086,88088,88400,88404,88406,88408,88440,88444,88446,88448,88460,88464,88466,88468,88480,88484,88486,88488,88600,88604,88606,88608,88640,88644,88646,88648,88660,88664,88666,88668,88680,88684,88686,88688,88800,88804,88806,88808,88840,88844,88846,88848,88860,88864,88866,88868,88880,88884,88886,88888,90000,90006,90009,90060,90066,90069,90090,90096,90099,90600,90606,90609,90660,90666,90669,90690,90696,90699,90900,90906,90909,90960,90966,90969,90990,90996,90999,94000,94006,94060,94066,94600,94660,94666,94900,96000,96006,96009,96060,96066,96069,96090,96096,96099,96400,96600,96606,96609,96640,96660,96664,96666,96669,96690,96696,96699,96900,96906,96909,96960,96966,96969,96990,96996,96999,99000,99006,99009,99060,99066,99069,99090,99096,99099,99600,99606,99609,99660,99666,99669,99690,99696,99699,99900,99906,99909,99960,99966,99969,99990,99996,99999,100000};
    int sum[100002];
    int i,k=0;
    sum[0]=1;sum[1]=2;sum[2]=2;
    for(i=3;i<100002;i++) {
        if(i==num[k]) {
            sum[i]=sum[i-1]+1;
            k++;
        }
        else {
            sum[i]=sum[i-1];
        }
    }
    int cases,A,B;scanf("%d",&cases);
    while(cases--) {
        scanf("%d%d",&A,&B);
        if(A>B) {
            printf("%d\n",sum[A]-sum[B-1]);
        }
        else {
            printf("%d\n",sum[B]-sum[A-1]);
        }
    }
    return 0;
}
 
 
 

I2luY2x1ZGU8c3RkaW8uaD4KI2luY2x1ZGU8c3RkbGliLmg+CmludCBtYWluKCkgewogICAgaW50IG51bVtdPXs0LDYsOCw5LDEwLDE4LDQwLDQ0LDQ2LDQ4LDQ5LDYwLDY0LDY2LDY4LDY5LDgwLDgxLDg0LDg2LDg4LDkwLDk0LDk2LDk5LDEwMCwxMDgsMTgwLDQwMCw0MDQsNDA2LDQwOCw0NDAsNDQ0LDQ0Niw0NDgsNDYwLDQ2NCw0NjYsNDY4LDQ2OSw0ODAsNDg0LDQ4Niw0ODgsNDkwLDQ5NCw0OTYsNjAwLDYwNCw2MDYsNjA4LDYwOSw2NDAsNjQ0LDY0Niw2NDgsNjQ5LDY2MCw2NjQsNjY2LDY2OCw2NjksNjgwLDY4NCw2ODYsNjg4LDY5MCw2OTQsNjk2LDY5OSw4MDAsODAxLDgwNCw4MDYsODA4LDgxMCw4MTgsODQwLDg0NCw4NDYsODQ4LDg2MCw4NjQsODY2LDg2OCw4ODAsODg0LDg4Niw4ODgsOTAwLDkwNiw5MDksOTQwLDk0Niw5NDksOTYwLDk2NCw5NjYsOTY5LDk5MCw5OTYsOTk5LDEwMDAsMTAwOCwxMDgwLDE4MDAsNDAwMCw0MDA0LDQwMDYsNDAwOCw0MDQwLDQwNDQsNDA0Niw0MDQ4LDQwNjAsNDA2NCw0MDY2LDQwNjgsNDA4MCw0MDg0LDQwODYsNDA4OCw0NDAwLDQ0MDQsNDQwNiw0NDA4LDQ0NDAsNDQ0NCw0NDQ2LDQ0NDgsNDQ2MCw0NDY0LDQ0NjYsNDQ2OCw0NDgwLDQ0ODQsNDQ4Niw0NDg4LDQ2MDAsNDYwNCw0NjA2LDQ2MDgsNDY0MCw0NjQ0LDQ2NDYsNDY0OCw0NjYwLDQ2NjQsNDY2Niw0NjY4LDQ2NjksNDY4MCw0Njg0LDQ2ODYsNDY4OCw0NjkwLDQ2OTQsNDY5Niw0ODAwLDQ4MDQsNDgwNiw0ODA4LDQ4NDAsNDg0NCw0ODQ2LDQ4NDgsNDg2MCw0ODY0LDQ4NjYsNDg2OCw0ODgwLDQ4ODQsNDg4Niw0ODg4LDQ5MDAsNDkwNiw0OTQwLDQ5NDYsNDk2MCw0OTY0LDQ5NjYsNjAwMCw2MDA0LDYwMDYsNjAwOCw2MDA5LDYwNDAsNjA0NCw2MDQ2LDYwNDgsNjA0OSw2MDYwLDYwNjQsNjA2Niw2MDY4LDYwNjksNjA4MCw2MDg0LDYwODYsNjA4OCw2MDkwLDYwOTQsNjA5Niw2MDk5LDY0MDAsNjQwNCw2NDA2LDY0MDgsNjQ0MCw2NDQ0LDY0NDYsNjQ0OCw2NDYwLDY0NjQsNjQ2Niw2NDY4LDY0ODAsNjQ4NCw2NDg2LDY0ODgsNjQ5MCw2NDk0LDY0OTYsNjYwMCw2NjA0LDY2MDYsNjYwOCw2NjA5LDY2NDAsNjY0NCw2NjQ2LDY2NDgsNjY0OSw2NjYwLDY2NjQsNjY2Niw2NjY4LDY2NjksNjY4MCw2Njg0LDY2ODYsNjY4OCw2NjkwLDY2OTQsNjY5Niw2Njk5LDY4MDAsNjgwNCw2ODA2LDY4MDgsNjg0MCw2ODQ0LDY4NDYsNjg0OCw2ODYwLDY4NjQsNjg2Niw2ODY4LDY4ODAsNjg4NCw2ODg2LDY4ODgsNjkwMCw2OTA2LDY5MDksNjk0MCw2OTQ2LDY5NjAsNjk2NCw2OTY2LDY5NjksNjk5MCw2OTk2LDY5OTksODAwMCw4MDAxLDgwMDQsODAwNiw4MDA4LDgwMTAsODAxOCw4MDQwLDgwNDQsODA0Niw4MDQ4LDgwNjAsODA2NCw4MDY2LDgwNjgsODA4MCw4MDg0LDgwODYsODA4OCw4MTAwLDgxMDgsODE4MCw4NDAwLDg0MDQsODQwNiw4NDA4LDg0NDAsODQ0NCw4NDQ2LDg0NDgsODQ2MCw4NDY0LDg0NjYsODQ2OCw4NDgwLDg0ODQsODQ4Niw4NDg4LDg2MDAsODYwNCw4NjA2LDg2MDgsODY0MCw4NjQ0LDg2NDYsODY0OCw4NjYwLDg2NjQsODY2Niw4NjY4LDg2ODAsODY4NCw4Njg2LDg2ODgsODgwMCw4ODA0LDg4MDYsODgwOCw4ODQwLDg4NDQsODg0Niw4ODQ4LDg4NjAsODg2NCw4ODY2LDg4NjgsODg4MCw4ODg0LDg4ODYsODg4OCw5MDAwLDkwMDYsOTAwOSw5MDYwLDkwNjYsOTA2OSw5MDkwLDkwOTYsOTA5OSw5NDAwLDk0MDYsOTQ2MCw5NDY2LDk0OTAsOTYwMCw5NjA2LDk2MDksOTY0MCw5NjYwLDk2NjQsOTY2Niw5NjY5LDk2OTAsOTY5Niw5Njk5LDk5MDAsOTkwNiw5OTA5LDk5NjAsOTk2Niw5OTY5LDk5OTAsOTk5Niw5OTk5LDEwMDAwLDEwMDA4LDEwMDgwLDEwODAwLDE4MDAwLDQwMDAwLDQwMDA0LDQwMDA2LDQwMDA4LDQwMDQwLDQwMDQ0LDQwMDQ2LDQwMDQ4LDQwMDYwLDQwMDY0LDQwMDY2LDQwMDY4LDQwMDgwLDQwMDg0LDQwMDg2LDQwMDg4LDQwNDAwLDQwNDA0LDQwNDA2LDQwNDA4LDQwNDQwLDQwNDQ0LDQwNDQ2LDQwNDQ4LDQwNDYwLDQwNDY0LDQwNDY2LDQwNDY4LDQwNDgwLDQwNDg0LDQwNDg2LDQwNDg4LDQwNjAwLDQwNjA0LDQwNjA2LDQwNjA4LDQwNjQwLDQwNjQ0LDQwNjQ2LDQwNjQ4LDQwNjYwLDQwNjY0LDQwNjY2LDQwNjY4LDQwNjgwLDQwNjg0LDQwNjg2LDQwNjg4LDQwODAwLDQwODA0LDQwODA2LDQwODA4LDQwODQwLDQwODQ0LDQwODQ2LDQwODQ4LDQwODYwLDQwODY0LDQwODY2LDQwODY4LDQwODgwLDQwODg0LDQwODg2LDQwODg4LDQ0MDAwLDQ0MDA0LDQ0MDA2LDQ0MDA4LDQ0MDQwLDQ0MDQ0LDQ0MDQ2LDQ0MDQ4LDQ0MDYwLDQ0MDY0LDQ0MDY2LDQ0MDY4LDQ0MDgwLDQ0MDg0LDQ0MDg2LDQ0MDg4LDQ0NDAwLDQ0NDA0LDQ0NDA2LDQ0NDA4LDQ0NDQwLDQ0NDQ0LDQ0NDQ2LDQ0NDQ4LDQ0NDYwLDQ0NDY0LDQ0NDY2LDQ0NDY4LDQ0NDgwLDQ0NDg0LDQ0NDg2LDQ0NDg4LDQ0NjAwLDQ0NjA0LDQ0NjA2LDQ0NjA4LDQ0NjQwLDQ0NjQ0LDQ0NjQ2LDQ0NjQ4LDQ0NjYwLDQ0NjY0LDQ0NjY2LDQ0NjY4LDQ0NjgwLDQ0Njg0LDQ0Njg2LDQ0Njg4LDQ0ODAwLDQ0ODA0LDQ0ODA2LDQ0ODA4LDQ0ODQwLDQ0ODQ0LDQ0ODQ2LDQ0ODQ4LDQ0ODYwLDQ0ODY0LDQ0ODY2LDQ0ODY4LDQ0ODgwLDQ0ODg0LDQ0ODg2LDQ0ODg4LDQ2MDAwLDQ2MDA0LDQ2MDA2LDQ2MDA4LDQ2MDQwLDQ2MDQ0LDQ2MDQ2LDQ2MDQ4LDQ2MDYwLDQ2MDY0LDQ2MDY2LDQ2MDY4LDQ2MDgwLDQ2MDg0LDQ2MDg2LDQ2MDg4LDQ2NDAwLDQ2NDA0LDQ2NDA2LDQ2NDA4LDQ2NDQwLDQ2NDQ0LDQ2NDQ2LDQ2NDQ4LDQ2NDYwLDQ2NDY0LDQ2NDY2LDQ2NDY4LDQ2NDgwLDQ2NDg0LDQ2NDg2LDQ2NDg4LDQ2NjAwLDQ2NjA0LDQ2NjA2LDQ2NjA4LDQ2NjQwLDQ2NjQ0LDQ2NjQ2LDQ2NjQ4LDQ2NjYwLDQ2NjY0LDQ2NjY2LDQ2NjY4LDQ2NjY5LDQ2NjgwLDQ2Njg0LDQ2Njg2LDQ2Njg4LDQ2NjkwLDQ2Njk0LDQ2Njk2LDQ2ODAwLDQ2ODA0LDQ2ODA2LDQ2ODA4LDQ2ODQwLDQ2ODQ0LDQ2ODQ2LDQ2ODQ4LDQ2ODYwLDQ2ODY0LDQ2ODY2LDQ2ODY4LDQ2ODgwLDQ2ODg0LDQ2ODg2LDQ2ODg4LDQ2OTAwLDQ2OTA2LDQ2OTQwLDQ2OTQ2LDQ2OTYwLDQ2OTY0LDQ2OTY2LDQ4MDAwLDQ4MDA0LDQ4MDA2LDQ4MDA4LDQ4MDQwLDQ4MDQ0LDQ4MDQ2LDQ4MDQ4LDQ4MDYwLDQ4MDY0LDQ4MDY2LDQ4MDY4LDQ4MDgwLDQ4MDg0LDQ4MDg2LDQ4MDg4LDQ4NDAwLDQ4NDA0LDQ4NDA2LDQ4NDA4LDQ4NDQwLDQ4NDQ0LDQ4NDQ2LDQ4NDQ4LDQ4NDYwLDQ4NDY0LDQ4NDY2LDQ4NDY4LDQ4NDgwLDQ4NDg0LDQ4NDg2LDQ4NDg4LDQ4NjAwLDQ4NjA0LDQ4NjA2LDQ4NjA4LDQ4NjQwLDQ4NjQ0LDQ4NjQ2LDQ4NjQ4LDQ4NjYwLDQ4NjY0LDQ4NjY2LDQ4NjY4LDQ4NjgwLDQ4Njg0LDQ4Njg2LDQ4Njg4LDQ4ODAwLDQ4ODA0LDQ4ODA2LDQ4ODA4LDQ4ODQwLDQ4ODQ0LDQ4ODQ2LDQ4ODQ4LDQ4ODYwLDQ4ODY0LDQ4ODY2LDQ4ODY4LDQ4ODgwLDQ4ODg0LDQ4ODg2LDQ4ODg4LDQ5MDAwLDQ5MDA2LDQ5MDYwLDQ5MDY2LDQ5NDAwLDQ5NDA2LDQ5NDYwLDQ5NDY2LDQ5NjAwLDQ5NjA2LDQ5NjQwLDQ5NjYwLDQ5NjY0LDQ5NjY2LDYwMDAwLDYwMDA0LDYwMDA2LDYwMDA4LDYwMDA5LDYwMDQwLDYwMDQ0LDYwMDQ2LDYwMDQ4LDYwMDQ5LDYwMDYwLDYwMDY0LDYwMDY2LDYwMDY4LDYwMDY5LDYwMDgwLDYwMDg0LDYwMDg2LDYwMDg4LDYwMDkwLDYwMDk0LDYwMDk2LDYwMDk5LDYwNDAwLDYwNDA0LDYwNDA2LDYwNDA4LDYwNDQwLDYwNDQ0LDYwNDQ2LDYwNDQ4LDYwNDYwLDYwNDY0LDYwNDY2LDYwNDY4LDYwNDgwLDYwNDg0LDYwNDg2LDYwNDg4LDYwNDkwLDYwNDk0LDYwNDk2LDYwNjAwLDYwNjA0LDYwNjA2LDYwNjA4LDYwNjA5LDYwNjQwLDYwNjQ0LDYwNjQ2LDYwNjQ4LDYwNjYwLDYwNjY0LDYwNjY2LDYwNjY4LDYwNjY5LDYwNjgwLDYwNjg0LDYwNjg2LDYwNjg4LDYwNjkwLDYwNjk0LDYwNjk2LDYwNjk5LDYwODAwLDYwODA0LDYwODA2LDYwODA4LDYwODQwLDYwODQ0LDYwODQ2LDYwODQ4LDYwODYwLDYwODY0LDYwODY2LDYwODY4LDYwODgwLDYwODg0LDYwODg2LDYwODg4LDYwOTAwLDYwOTA2LDYwOTA5LDYwOTQwLDYwOTQ2LDYwOTYwLDYwOTY0LDYwOTY2LDYwOTY5LDYwOTkwLDYwOTk2LDYwOTk5LDY0MDAwLDY0MDA0LDY0MDA2LDY0MDA4LDY0MDQwLDY0MDQ0LDY0MDQ2LDY0MDQ4LDY0MDYwLDY0MDY0LDY0MDY2LDY0MDY4LDY0MDgwLDY0MDg0LDY0MDg2LDY0MDg4LDY0NDAwLDY0NDA0LDY0NDA2LDY0NDA4LDY0NDQwLDY0NDQ0LDY0NDQ2LDY0NDQ4LDY0NDYwLDY0NDY0LDY0NDY2LDY0NDY4LDY0NDgwLDY0NDg0LDY0NDg2LDY0NDg4LDY0NjAwLDY0NjA0LDY0NjA2LDY0NjA4LDY0NjQwLDY0NjQ0LDY0NjQ2LDY0NjQ4LDY0NjYwLDY0NjY0LDY0NjY2LDY0NjY4LDY0NjgwLDY0Njg0LDY0Njg2LDY0Njg4LDY0ODAwLDY0ODA0LDY0ODA2LDY0ODA4LDY0ODQwLDY0ODQ0LDY0ODQ2LDY0ODQ4LDY0ODYwLDY0ODY0LDY0ODY2LDY0ODY4LDY0ODgwLDY0ODg0LDY0ODg2LDY0ODg4LDY0OTAwLDY0OTA2LDY0OTQwLDY0OTQ2LDY0OTYwLDY0OTY0LDY0OTY2LDY2MDAwLDY2MDA0LDY2MDA2LDY2MDA4LDY2MDA5LDY2MDQwLDY2MDQ0LDY2MDQ2LDY2MDQ4LDY2MDQ5LDY2MDYwLDY2MDY0LDY2MDY2LDY2MDY4LDY2MDY5LDY2MDgwLDY2MDg0LDY2MDg2LDY2MDg4LDY2MDkwLDY2MDk0LDY2MDk2LDY2MDk5LDY2NDAwLDY2NDA0LDY2NDA2LDY2NDA4LDY2NDQwLDY2NDQ0LDY2NDQ2LDY2NDQ4LDY2NDYwLDY2NDY0LDY2NDY2LDY2NDY4LDY2NDgwLDY2NDg0LDY2NDg2LDY2NDg4LDY2NDkwLDY2NDk0LDY2NDk2LDY2NjAwLDY2NjA0LDY2NjA2LDY2NjA4LDY2NjA5LDY2NjQwLDY2NjQ0LDY2NjQ2LDY2NjQ4LDY2NjQ5LDY2NjYwLDY2NjY0LDY2NjY2LDY2NjY4LDY2NjY5LDY2NjgwLDY2Njg0LDY2Njg2LDY2Njg4LDY2NjkwLDY2Njk0LDY2Njk2LDY2Njk5LDY2ODAwLDY2ODA0LDY2ODA2LDY2ODA4LDY2ODQwLDY2ODQ0LDY2ODQ2LDY2ODQ4LDY2ODYwLDY2ODY0LDY2ODY2LDY2ODY4LDY2ODgwLDY2ODg0LDY2ODg2LDY2ODg4LDY2OTAwLDY2OTA2LDY2OTA5LDY2OTQwLDY2OTQ2LDY2OTYwLDY2OTY0LDY2OTY2LDY2OTY5LDY2OTkwLDY2OTk2LDY2OTk5LDY4MDAwLDY4MDA0LDY4MDA2LDY4MDA4LDY4MDQwLDY4MDQ0LDY4MDQ2LDY4MDQ4LDY4MDYwLDY4MDY0LDY4MDY2LDY4MDY4LDY4MDgwLDY4MDg0LDY4MDg2LDY4MDg4LDY4NDAwLDY4NDA0LDY4NDA2LDY4NDA4LDY4NDQwLDY4NDQ0LDY4NDQ2LDY4NDQ4LDY4NDYwLDY4NDY0LDY4NDY2LDY4NDY4LDY4NDgwLDY4NDg0LDY4NDg2LDY4NDg4LDY4NjAwLDY4NjA0LDY4NjA2LDY4NjA4LDY4NjQwLDY4NjQ0LDY4NjQ2LDY4NjQ4LDY4NjYwLDY4NjY0LDY4NjY2LDY4NjY4LDY4NjgwLDY4Njg0LDY4Njg2LDY4Njg4LDY4ODAwLDY4ODA0LDY4ODA2LDY4ODA4LDY4ODQwLDY4ODQ0LDY4ODQ2LDY4ODQ4LDY4ODYwLDY4ODY0LDY4ODY2LDY4ODY4LDY4ODgwLDY4ODg0LDY4ODg2LDY4ODg4LDY5MDAwLDY5MDA2LDY5MDA5LDY5MDYwLDY5MDY2LDY5MDY5LDY5MDkwLDY5MDk2LDY5MDk5LDY5NDAwLDY5NDA2LDY5NDYwLDY5NDY2LDY5NjAwLDY5NjA2LDY5NjA5LDY5NjQwLDY5NjYwLDY5NjY0LDY5NjY2LDY5NjY5LDY5NjkwLDY5Njk2LDY5Njk5LDY5OTAwLDY5OTA2LDY5OTA5LDY5OTYwLDY5OTY2LDY5OTY5LDY5OTkwLDY5OTk2LDY5OTk5LDgwMDAwLDgwMDAxLDgwMDA0LDgwMDA2LDgwMDA4LDgwMDEwLDgwMDE4LDgwMDQwLDgwMDQ0LDgwMDQ2LDgwMDQ4LDgwMDYwLDgwMDY0LDgwMDY2LDgwMDY4LDgwMDgwLDgwMDg0LDgwMDg2LDgwMDg4LDgwMTAwLDgwMTA4LDgwMTgwLDgwNDAwLDgwNDA0LDgwNDA2LDgwNDA4LDgwNDQwLDgwNDQ0LDgwNDQ2LDgwNDQ4LDgwNDYwLDgwNDY0LDgwNDY2LDgwNDY4LDgwNDgwLDgwNDg0LDgwNDg2LDgwNDg4LDgwNjAwLDgwNjA0LDgwNjA2LDgwNjA4LDgwNjQwLDgwNjQ0LDgwNjQ2LDgwNjQ4LDgwNjYwLDgwNjY0LDgwNjY2LDgwNjY4LDgwNjgwLDgwNjg0LDgwNjg2LDgwNjg4LDgwODAwLDgwODA0LDgwODA2LDgwODA4LDgwODQwLDgwODQ0LDgwODQ2LDgwODQ4LDgwODYwLDgwODY0LDgwODY2LDgwODY4LDgwODgwLDgwODg0LDgwODg2LDgwODg4LDgxMDAwLDgxMDA4LDgxMDgwLDgxODAwLDg0MDAwLDg0MDA0LDg0MDA2LDg0MDA4LDg0MDQwLDg0MDQ0LDg0MDQ2LDg0MDQ4LDg0MDYwLDg0MDY0LDg0MDY2LDg0MDY4LDg0MDgwLDg0MDg0LDg0MDg2LDg0MDg4LDg0NDAwLDg0NDA0LDg0NDA2LDg0NDA4LDg0NDQwLDg0NDQ0LDg0NDQ2LDg0NDQ4LDg0NDYwLDg0NDY0LDg0NDY2LDg0NDY4LDg0NDgwLDg0NDg0LDg0NDg2LDg0NDg4LDg0NjAwLDg0NjA0LDg0NjA2LDg0NjA4LDg0NjQwLDg0NjQ0LDg0NjQ2LDg0NjQ4LDg0NjYwLDg0NjY0LDg0NjY2LDg0NjY4LDg0NjgwLDg0Njg0LDg0Njg2LDg0Njg4LDg0ODAwLDg0ODA0LDg0ODA2LDg0ODA4LDg0ODQwLDg0ODQ0LDg0ODQ2LDg0ODQ4LDg0ODYwLDg0ODY0LDg0ODY2LDg0ODY4LDg0ODgwLDg0ODg0LDg0ODg2LDg0ODg4LDg2MDAwLDg2MDA0LDg2MDA2LDg2MDA4LDg2MDQwLDg2MDQ0LDg2MDQ2LDg2MDQ4LDg2MDYwLDg2MDY0LDg2MDY2LDg2MDY4LDg2MDgwLDg2MDg0LDg2MDg2LDg2MDg4LDg2NDAwLDg2NDA0LDg2NDA2LDg2NDA4LDg2NDQwLDg2NDQ0LDg2NDQ2LDg2NDQ4LDg2NDYwLDg2NDY0LDg2NDY2LDg2NDY4LDg2NDgwLDg2NDg0LDg2NDg2LDg2NDg4LDg2NjAwLDg2NjA0LDg2NjA2LDg2NjA4LDg2NjQwLDg2NjQ0LDg2NjQ2LDg2NjQ4LDg2NjYwLDg2NjY0LDg2NjY2LDg2NjY4LDg2NjgwLDg2Njg0LDg2Njg2LDg2Njg4LDg2ODAwLDg2ODA0LDg2ODA2LDg2ODA4LDg2ODQwLDg2ODQ0LDg2ODQ2LDg2ODQ4LDg2ODYwLDg2ODY0LDg2ODY2LDg2ODY4LDg2ODgwLDg2ODg0LDg2ODg2LDg2ODg4LDg4MDAwLDg4MDA0LDg4MDA2LDg4MDA4LDg4MDQwLDg4MDQ0LDg4MDQ2LDg4MDQ4LDg4MDYwLDg4MDY0LDg4MDY2LDg4MDY4LDg4MDgwLDg4MDg0LDg4MDg2LDg4MDg4LDg4NDAwLDg4NDA0LDg4NDA2LDg4NDA4LDg4NDQwLDg4NDQ0LDg4NDQ2LDg4NDQ4LDg4NDYwLDg4NDY0LDg4NDY2LDg4NDY4LDg4NDgwLDg4NDg0LDg4NDg2LDg4NDg4LDg4NjAwLDg4NjA0LDg4NjA2LDg4NjA4LDg4NjQwLDg4NjQ0LDg4NjQ2LDg4NjQ4LDg4NjYwLDg4NjY0LDg4NjY2LDg4NjY4LDg4NjgwLDg4Njg0LDg4Njg2LDg4Njg4LDg4ODAwLDg4ODA0LDg4ODA2LDg4ODA4LDg4ODQwLDg4ODQ0LDg4ODQ2LDg4ODQ4LDg4ODYwLDg4ODY0LDg4ODY2LDg4ODY4LDg4ODgwLDg4ODg0LDg4ODg2LDg4ODg4LDkwMDAwLDkwMDA2LDkwMDA5LDkwMDYwLDkwMDY2LDkwMDY5LDkwMDkwLDkwMDk2LDkwMDk5LDkwNjAwLDkwNjA2LDkwNjA5LDkwNjYwLDkwNjY2LDkwNjY5LDkwNjkwLDkwNjk2LDkwNjk5LDkwOTAwLDkwOTA2LDkwOTA5LDkwOTYwLDkwOTY2LDkwOTY5LDkwOTkwLDkwOTk2LDkwOTk5LDk0MDAwLDk0MDA2LDk0MDYwLDk0MDY2LDk0NjAwLDk0NjYwLDk0NjY2LDk0OTAwLDk2MDAwLDk2MDA2LDk2MDA5LDk2MDYwLDk2MDY2LDk2MDY5LDk2MDkwLDk2MDk2LDk2MDk5LDk2NDAwLDk2NjAwLDk2NjA2LDk2NjA5LDk2NjQwLDk2NjYwLDk2NjY0LDk2NjY2LDk2NjY5LDk2NjkwLDk2Njk2LDk2Njk5LDk2OTAwLDk2OTA2LDk2OTA5LDk2OTYwLDk2OTY2LDk2OTY5LDk2OTkwLDk2OTk2LDk2OTk5LDk5MDAwLDk5MDA2LDk5MDA5LDk5MDYwLDk5MDY2LDk5MDY5LDk5MDkwLDk5MDk2LDk5MDk5LDk5NjAwLDk5NjA2LDk5NjA5LDk5NjYwLDk5NjY2LDk5NjY5LDk5NjkwLDk5Njk2LDk5Njk5LDk5OTAwLDk5OTA2LDk5OTA5LDk5OTYwLDk5OTY2LDk5OTY5LDk5OTkwLDk5OTk2LDk5OTk5LDEwMDAwMH07CiAgICBpbnQgc3VtWzEwMDAwMl07CiAgICBpbnQgaSxrPTA7CiAgICBzdW1bMF09MTtzdW1bMV09MjtzdW1bMl09MjsKICAgIGZvcihpPTM7aTwxMDAwMDI7aSsrKSB7CiAgICAgICAgaWYoaT09bnVtW2tdKSB7CiAgICAgICAgICAgIHN1bVtpXT1zdW1baS0xXSsxOwogICAgICAgICAgICBrKys7CiAgICAgICAgfQogICAgICAgIGVsc2UgewogICAgICAgICAgICBzdW1baV09c3VtW2ktMV07CiAgICAgICAgfQogICAgfQogICAgaW50IGNhc2VzLEEsQjtzY2FuZigiJWQiLCZjYXNlcyk7CiAgICB3aGlsZShjYXNlcy0tKSB7CiAgICAgICAgc2NhbmYoIiVkJWQiLCZBLCZCKTsKICAgICAgICBpZihBPkIpIHsKICAgICAgICAgICAgcHJpbnRmKCIlZFxuIixzdW1bQV0tc3VtW0ItMV0pOwogICAgICAgIH0KICAgICAgICBlbHNlIHsKICAgICAgICAgICAgcHJpbnRmKCIlZFxuIixzdW1bQl0tc3VtW0EtMV0pOwogICAgICAgIH0KICAgIH0KICAgIHJldHVybiAwOwp9CgoK

MgozIDUKMiAz

2
3 5
2 3