不解释(因为蒟蒻太弱了，肝了一晚受不了了。。。现在省选退役，这有可能就是我做的最后一题了。。。
#include<bits/stdc++.h> using namespace std; #define ll long long const int N=100000005,mod=998244353; int cc,pr[N/10],sz[1000005],szz[1000005],tb[101005],tg[20000005];bool vv[20000005],vis[N],ans[1000005];ll ti[1000005]; int t1[7171]={263,60,120,128,718,130,322,138,86,18,44,50,89,1001,79,11,56,114,54,105,73,162,180,45,268,95,212,52,170,114,133,63,117,161,186,66,138,6,184,203,255,192,28,128,17,23,92,130,228,240,354,33,60,451,21,157,118,428,42,142,56,58,170,41,331,77,65,31,7,18,46,474,139,265,46,140,40,81,33,188,214,138,62,70,22,212,644,13,156,287,210,36,75,56,289,94,210,182,252,8,664,32,9,40,87,61,155,60,234,10,42,50,258,222,166,79,400,229,192,122,12,44,50,42,14,94,276,49,628,331,86,180,347,25,326,480,334,98,185,99,120,66,151,163,28,17,795,110,291,125,546,180,156,302,112,118,81,101,275,381,232,128,48,131,1,231,97,12,222,110,155,41,36,96,50,121,651,150,18,130,250,42,12,124,30,240,41,121,128,36,83,65,102,38,238,80,56,92,84,156,140,124,233,109,167,35,98,235,599,49,53,54,18,68,58,49,72,5,96,234,29,201,67,53,150,6,30,269,169,56,80,86,4,164,10,72,54,117,17,179,91,24,40,137,39,33,69,94,240,264,60,14,11,181,28,99,21,39,59,130,408,12,252,162,70,80,158,1,159,122,155,55,6,75,36,21,178,53,492,57,16,26,214,23,27,210,166,33,27,26,119,139,33,276,195,82,38,306,67,359,60,349,21,84,90,37,113,2,30,180,18,136,4,26,416,114,40,145,41,128,202,8,42,159,140,29,67,108,19,16,320,156,34,72,294,66,7,23,261,53,18,580,100,42,214,60,50,76,96,102,112,306,150,128,137,188,197,352,32,70,20,178,222,48,198,12,67,85,136,438,245,361,6,105,135,554,84,12,207,348,55,144,50,427,140,123,225,99,12,28,212,197,235,52,13,187,396,30,279,379,54,42,50,18,36,6,91,137,138,70,194,13,213,2,173,139,46,30,404,24,213,469,204,19,67,88,57,53,124,162,1050,38,314,146,230,28,284,18,58,35,75,114,126,12,520,13,155,81,39,46,27,349,34,312,246,52,28,35,263,120,150,86,12,262,23,3,84,442,404,172,12,326,72,478,32,94,313,337,76,24,15,132,107,98,304,168,214,101,97,350,420,9,31,158,36,168,10,36,42,68,119,101,120,439,61,96,154,210,104,256,160,74,1,37,60,24,270,120,349,125,154,253,179,1058,286,205,1,208,590,82,64,86,48,6,26,118,270,13,16,349,68,10,118,14,18,44,56,296,294,144,9,29,30,61,3,44,90,400,56,14,160,66,24,74,146,200,42,192,97,9,210,152,324,76,8,10,3,11,190,380,112,428,46,146,24,12,275,115,252,357,1,312,132,27,263,30,168,6,213,27,126,18,486,102,10,408,64,23,119,126,2,62,108,86,154,108,222,32,34,252,104,228,46,157,107,216,210,294,1,77,290,802,42,26,130,104,46,24,571,109,135,232,639,5,391,44,24,138,131,35,24,152,41,56,327,6,66,17,32,173,66,117,75,180,101,121,66,194,346,20,240,214,91,289,132,32,46,473,53,6,36,30,30,224,28,38,112,30,140,172,398,6,94,290,6,42,168,66,90,156,18,219,193,8,394,438,380,22,146,30,37,159,61,55,198,171,73,140,268,150,18,42,74,288,96,66,177,13,24,162,14,126,328,2,930,64,168,222,354,277,473,266,90,90,253,425,280,62,36,257,425,500,10,116,101,36,19,18,40,122,16,18,186,284,24,104,74,60,243,51,8,90,130,126,56,24,126,161,109,168,118,30,20,275,12,31,46,24,42,188,214,152,99,31,1457,67,36,228,150,94,494,78,121,83,30,432,176,148,530,8,22,159,133,7,215,308,2,32,86,72,22,506,354,18,70,410,72,101,124,235,146,82,48,8,437,77,7,193,23,265,164,111,467,2,310,60,66,68,84,96,156,340,142,64,60,229,53,316,115,119,60,206,30,334,2,40,361,7,118,74,6,4,115,395,186,32,206,413,33,24,32,84,220,450,254,34,21,89,90,69,7,25,360,115,36,10,414,246,216,24,74,520,62,174,36,198,330,57,193,114,9,101,180,167,275,400,44,489,24,863,28,62,114,124,206,150,112,8,60,234,6,141,241,104,148,126,146,46,72,72,248,16,26,139,249,32,208,110,77,27,56,198,174,78,162,80,154,20,95,167,224,286,140,183,152,107,124,64,166,156,30,270,290,462,48,148,183,39,124,56,50,912,76,22,200,42,567,129,252,308,4,114,413,97,27,208,215,26,94,80,276,370,30,50,156,176,79,43,60,182,152,506,354,306,56,336,4,26,130,128,130,6,240,38,280,20,11,3,316,305,143,18,554,198,90,70,48,83,21,6,17,113,3,191,12,148,390,120,42,198,92,24,72,64,54,276,73,61,286,20,120,134,263,209,114,88,108,74,46,14,4,279,15,86,112,152,90,33,27,382,8,240,132,4,126,60,65,116,25,94,26,240,162,130,66,194,180,55,341,12,208,66,132,386,226,164,282,40,78,141,47,238,414,216,72,2,12,27,127,12,94,134,233,159,70,444,227,43,6,404,815,145,426,54,280,691,37,136,90,110,52,204,52,4,312,31,35,82,95,247,128,102,47,536,93,80,64,239,51,246,186,234,459,111,274,115,215,126,235,7,322,18,144,13,27,44,476,48,42,108,138,814,95,36,135,72,186,226,18,6,25,71,14,210,376,210,306,332,12,41,77,6,32,1,257,90,42,72,372,54,60,36,148,70,136,147,83,362,164,6,9,620,55,177,164,313,92,11,988,515,21,15,240,48,153,28,65,80,54,54,36,144,30,76,390,72,24,56,111,141,160,96,104,42,60,90,144,382,74,156,56,64,88,290,42,108,442,21,281,292,31,380,65,50,1,21,48,168,66,146,160,112,102,50,19,89,88,27,17,3,4,149,183,113,152,72,11,120,577,444,278,300,58,20,66,90,78,17,73,106,44,57,72,44,415,141,7,201,125,18,132,238,156,42,54,140,70,90,74,61,201,50,145,236,27,42,624,71,179,365,189,551,331,334,40,44,126,84,42,51,21,230,385,51,174,211,1,186,220,89,51,24,246,252,232,22,153,133,96,107,515,169,40,15,73,84,8,236,77,152,388,187,11,637,72,71,30,114,244,166,78,60,430,236,232,62,193,59,32,56,98,172,288,288,128,94,110,363,87,78,63,564,25,142,82,482,64,22,66,162,175,136,37,44,212,63,25,88,67,563,12,85,56,43,213,25,184,204,360,92,4,58,21,161,363,9,20,252,40,182,6,144,8,260,76,160,192,130,210,54,198,270,176,202,24,44,52,168,30,270,182,5,279,130,4,296,64,195,333,12,3,33,458,226,174,133,43,209,257,330,38,468,312,138,30,55,12,24,177,420,282,144,18,134,22,146,6,114,390,26,121,217,178,406,70,218,30,176,190,108,12,11,175,280,85,31,156,46,78,326,54,108,76,180,370,100,10,50,150,90,298,50,220,192,343,47,20,112,66,168,122,22,122,78,44,316,52,107,1,272,100,38,10,4,38,85,89,96,108,428,18,61,81,66,28,20,126,48,36,71,79,324,576,144,140,22,439,499,130,162,5,144,57,4,92,262,96,12,170,58,2,10,8,26,196,226,204,89,111,30,48,390,4,170,44,196,240,28,36,14,220,392,106,84,66,30,464,516,30,52,14,94,210,150,24,180,74,364,94,154,114,58,128,79,249,386,256,248,246,4,192,54,100,1,457,92,34,182,107,137,8,106,110,82,60,134,96,78,540,4,108,32,198,94,180,236,112,210,72,50,144,76,117,328,241,154,137,159,209,191,212,85,123,134,160,20,10,228,78,134,28,21,45,294,170,72,174,22,184,38,80,132,130,91,17,20,222,10,91,232,195,508,48,44,106,62,173,60,97,268,240,115,36,139,222,148,114,153,203,126,174,34,184,274,105,3,694,188,78,117,33,4,156,342,344,144,65,1,171,187,66,120,186,74,43,11,221,311,24,104,22,151,360,179,318,50,120,166,14,41,379,132,169,299,22,174,114,8,156,78,82,164,4,183,5,262,36,422,190,145,127,238,42,20,341,5,150,230,280,43,7,510,322,357,623,142,8,300,227,349,208,114,120,254,94,217,324,39,10,94,162,126,38,76,96,55,305,44,19,21,3,21,178,52,65,79,42,274,54,95,160,41,3,193,20,24,186,24,5,235,82,242,28,144,272,4,80,28,116,72,18,286,318,28,146,98,410,41,101,75,92,65,158,69,164,324,275,180,18,56,274,270,36,174,121,275,26,6,328,516,140,238,378,60,614,59,88,48,135,12,52,20,70,363,11,128,8,56,190,494,76,236,89,91,168,304,212,81,7,30,80,12,59,169,10,66,252,20,114,108,208,54,15,29,706,114,55,137,140,4,8,90,88,97,113,14,156,78,499,123,102,31,97,70,140,197,37,474,6,58,306,54,145,245,86,156,34,6,173,128,7,78,294,498,48,78,154,339,423,86,67,273,164,180,6,69,141,358,84,20,156,264,73,65,102,196,2,656,8,48,258,204,36,17,183,533,325,44,218,101,19,42,454,374,76,296,436,314,2,46,81,116,243,42,138,953,568,93,178,36,584,104,4,152,82,84,330,210,292,55,49,400,86,18,88,24,131,121,140,14,9,145,411,19,338,36,56,178,144,16,20,436,137,95,29,52,7,250,112,52,154,145,40,313,180,164,124,32,455,5,74,28,69,11,66,16,18,37,169,98,85,139,12,62,171,57,106,12,233,79,290,142,172,164,320,213,121,8,12,24,22,25,81,16,156,120,4,86,120,184,281,25,346,44,30,6,13,115,88,17,21,11,32,167,214,486,132,2,72,54,6,70,60,116,69,500,253,66,154,242,41,157,40,92,28,110,12,186,54,46,110,292,96,26,180,70,342,128,87,164,203,132,81,117,150,37,247,210,118,480,441,261,50,412,318,3,299,277,63,24,56,245,61,112,30,132,8,76,14,180,118,138,486,30,354,260,592,128,48,113,364,1,40,218,278,12,316,391,113,108,32,312,34,350,4,23,375,77,35,218,207,25,18,78,242,193,69,200,23,29,259,96,32,257,216,36,90,210,132,16,30,84,528,158,84,402,4,30,66,120,120,308,245,115,46,42,114,14,20,20,28,38,104,112,192,163,115,120,29,91,28,86,114,302,2,140,132,366,658,88,472,12,240,398,154,44,158,30,174,152,70,368,4,12,110,30,10,236,51,67,372,46,3,33,91,207,312,102,306,184,54,122,138,12,184,10,148,100,172,68,20,69,7,158,78,10,6,273,111,10,4,214,98,119,259,136,266,175,88,601,210,10,54,182,463,57,282,12,254,22,12,40,550,76,422,162,52,203,215,73,3,84,5,151,105,45,42,70,59,19,213,239,48,60,390,96,36,192,39,109,182,18,632,20,72,30,344,330,250,522,131,169,272,82,144,189,15,72,49,257,42,133,163,166,15,39,74,36,162,244,330,14,274,39,189,235,295,178,211,352,8,121,94,134,120,84,52,14,136,248,9,228,3,153,267,76,70,222,52,9,340,17,54,66,6,154,36,404,215,1,84,160,4,220,88,254,106,402,122,138,57,145,110,21,49,234,104,77,27,32,109,157,24,4,110,6,154,56,505,81,38,108,174,10,68,52,68,72,86,188,82,44,476,5,319,180,130,198,536,454,331,227,64,530,19,481,138,126,75,185,200,254,160,120,168,114,26,184,244,50,2,28,42,19,23,56,250,110,6,48,148,171,129,79,119,97,125,62,165,27,30,268,150,108,74,87,9,82,8,37,264,292,395,541,395,12,54,80,24,11,73,100,12,18,165,40,127,144,30,268,138,110,223,68,1,115,25,16,110,216,150,94,106,7,39,4,138,84,152,126,60,34,626,16,138,416,96,88,55,29,131,21,16,140,84,4,6,84,650,52,54,38,32,282,698,80,250,234,56,126,34,38,36,61,51,18,104,102,150,55,69,36,188,67,152,217,210,32,60,30,42,136,269,12,191,44,13,36,455,56,88,252,5,77,63,36,4,17,175,117,32,207,61,71,243,418,331,81,122,182,38,100,10,60,156,12,378,18,42,93,16,83,90,66,72,52,122,26,38,130,32,18,203,544,48,291,24,236,30,178,68,172,2,87,151,65,4,141,102,158,216,220,60,162,217,124,93,16,192,7,61,304,140,182,104,110,18,57,139,104,64,277,61,22,398,299,61,138,125,5,107,311,73,375,76,41,13,15,9,102,18,56,4,32,18,10,66,305,135,270,66,138,134,152,18,326,100,120,192,34,74,66,56,70,198,54,42,44,270,486,54,34,206,96,106,110,84,280,8,142,48,59,157,152,130,140,4,61,259,10,44,158,14,470,58,324,128,171,69,34,144,93,71,49,172,91,58,108,32,70,66,86,30,154,46,94,84,49,69,162,146,8,23,111,129,404,271,81,125,310,377,103,8,130,174,116,10,31,316,283,30,42,12,272,5,84,55,526,80,6,8,18,136,310,226,76,288,23,283,34,126,254,176,2,44,94,374,74,424,51,369,43,184,9,208,306,233,213,88,59,41,284,71,103,30,16,50,214,163,95,18,504,188,130,269,17,176,50,173,47,38,118,1,31,340,552,116,480,42,42,60,42,23,95,205,545,230,486,70,273,167,66,34,9,73,14,68,42,10,1,17,402,57,339,504,49,65,6,201,263,72,18,10,53,69,4,55,153,19,129,214,84,84,6,92,144,28,180,218,40,88,117,257,119,201,10,193,217,287,301,31,149,50,185,173,106,486,12,98,244,6,872,52,416,22,288,38,110,34,198,60,21,7,14,162,32,22,202,78,39,19,34,231,33,154,162,158,16,317,172,69,276,96,326,169,185,366,28,12,201,101,240,6,6,184,44,102,88,240,244,142,234,570,786,396,154,55,93,404,168,4,10,22,150,224,125,35,140,70,246,38,134,181,111,30,196,156,102,80,88,8,282,294,258,216,147,315,64,926,178,372,8,29,16,25,227,255,148,62,94,208,26,80,95,427,364,146,178,62,91,51,154,46,88,20,28,216,380,88,62,84,76,631,59,60,168,193,139,92,322,47,167,162,96,198,104,162,52,8,70,66,158,280,324,98,328,210,2,124,78,140,10,119,193,134,102,179,11,24,140,66,28,240,150,457,67,17,29,212,47,25,238,110,51,427,20,124,2,144,90,36,29,65,54,140,142,219,95,209,121,214,422,130,36,420,37,215,32,144,114,312,119,153,87,85,43,329,24,18,557,29,220,26,49,36,61,136,66,296,126,46,78,180,66,30,236,190,150,114,44,157,455,84,40,84,72,92,18,51,163,230,67,21,240,192,215,43,78,18,273,304,125,24,30,60,292,184,4,108,306,180,102,65,39,160,170,216,78,36,185,144,252,12,151,222,178,93,83,6,132,102,70,218,16,44,106,590,12,290,20,110,29,36,93,32,294,57,41,215,83,561,317,34,10,371,100,325,192,10,138,24,40,118,153,120,81,258,162,62,334,22,212,244,56,250,90,49,29,446,82,2,16,176,76,38,84,370,146,63,159,206,28,24,102,437,515,18,32,43,113,291,95,46,160,18,53,39,93,397,54,57,203,4,192,272,186,155,41,172,196,330,17,180,1,179,25,18,72,126,60,322,122,448,47,111,97,24,21,92,106,72,73,163,42,128,92,194,362,67,109,4,82,40,24,102,198,301,60,371,14,22,90,404,312,58,426,152,460,98,240,137,96,331,94,7,175,208,52,110,110,168,196,325,293,339,347,261,791,274,608,200,32,122,252,152,21,81,30,140,224,32,148,60,125,447,157,25,27,33,22,13,148,79,422,96,100,84,48,86,82,71,24,61,40,74,170,28,188,276,246,82,183,87,38,294,70,128,148,152,204,30,66,102,77,48,853,7,33,174,264,86,130,176,70,438,332,58,216,164,34,5,25,18,200,64,73,577,79,29,198,54,120,88,102,128,2,164,350,156,182,274,14,208,67,45,104,174,48,312,161,139,130,27,65,94,14,31,267,74,40,26,88,252,62,28,67,13,12,10,1,1,174,40,116,6,124,318,8,192,69,51,120,112,324,254,50,20,496,80,34,2,36,32,22,126,48,9,201,384,2,657,175,77,129,74,232,37,255,102,96,12,122,156,105,372,295,38,111,45,4,272,102,408,130,94,89,433,46,46,79,61,366,4,42,68,150,184,236,342,39,441,119,41,40,28,34,146,22,168,32,184,48,366,410,97,95,180,264,46,150,144,168,530,42,136,74,190,90,114,56,18,78,65,17,92,168,132,36,262,61,287,42,38,53,41,119,25,6,245,25,104,619,65,196,20,103,93,36,308,54,328,558,162,161,63,16,170,112,26,29,83,12,380,142,140,66,94,8,152,226,94,86,12,30,14,293,149,112,102,122,11,247,246,420,59,127,37,25,4,334,14,252,108,202,376,118,228,23,197,18,37,27,44,126,204,120,59,149,1135,133,176,30,18,70,110,3,135,138,256,72,78,10,75,35,320,432,106,20,10,282,192,2,226,36,282,132,30,54,198,258,2,38,68,132,17,16,51,22,159,49,94,20,506,107,69,199,65,14,177,224,113,11,61,78,62,88,407,172,11,246,366,109,100,127,192,6,52,10,61,351,52,120,352,56,48,194,226,534,84,407,9,240,36,10,260,94,90,90,6,98,64,123,47,76,144,42,14,136,94,99,77,98,46,378,116,30,159,261,12,90,28,50,90,28,74,40,190,160,190,84,74,86,6,164,384,132,13,27,17,184,7,18,370,8,6,90,298,270,20,18,250,164,130,259,131,60,26,10,72,338,224,244,6,276,60,69,99,64,6,863,584,317,290,112,6,14,357,37,84,31,308,779,34,6,98,54,6,68,76,11,107,50,342,150,287,121,160,32,10,78,32,43,35,270,54,294,42,72,192,46,240,248,220,104,28,68,114,78,30,90,210,22,266,54,60,6,112,314,35,61,240,51,188,36,25,250,392,46,120,32,52,10,170,126,146,600,46,200,88,72,98,30,70,39,53,368,304,434,192,46,160,230,136,80,93,468,81,676,14,90,76,126,44,245,79,78,112,35,97,319,275,6,44,71,96,31,206,2,60,30,768,308,100,54,150,19,371,78,227,243,137,121,130,133,68,13,20,30,96,2,132,258,18,47,73,562,26,136,186,78,380,250,104,60,156,52,134,10,96,22,50,282,36,99,323,596,82,120,264,458,160,150,120,52,14,9,15,168,204,136,133,731,114,56,328,36,56,400,138,88,8,80,16,145,540,5,360,146,390,318,176,72,16,186,103,84,3,30,92,207,345,142,145,8,21,67,67,57,169,607,47,182,28,195,259,16,118,30,152,42,394,326,138,58,20,83,11,137,399,220,152,120,113,97,39,8,120,155,96,162,48,260,23,7,40,701,37,115,11,254,144,19,203,66,94,288,50,76,20,16,82,21,91,240,124,121,268,3,4,96,68,406,470,64,468,110,28,72,104,132,126,309,39,65,29,50,41,323,26,66,208,49,23,78,12,24,24,324,6,146,83,8,135,30,102,245,20,287,108,276,148,44,60,890,19,59,402,54,216,84,220,156,222,20,83,45,2,288,62,318,148,222,264,114,14,11,31,34,20,142,320,52,393,237,391,97,31,173,51,73,354,62,254,2,158,40,464,173,83,110,396,40,68,438,53,197,14,341,157,210,53,73,98,292,8,22,191,305,138,110,208,68,112,224,30,48,9,33,671,265,166,206,146,397,37,104,94,14,150,4,134,15,181,20,52,2,126,40,58,364,378,16,59,45,16,143,179,269,624,51,70,212,102,14,107,133,235,43,504,112,130,210,73,25,262,158,132,228,68,100,158,1214,90,37,5,94,153,331,532,168,193,268,124,15,132,78,8,46,22,14,122,6,16,116,42,78,40,78,44,462,120,18,310,8,262,186,360,293,49,168,110,84,16,76,116,72,48,120,41,220,49,82,57,44,221,318,97,61,82,48,222,35,123,154,16,195,49,60,166,72,42,20,154,153,273,60,66,42,2,40,116,245,32,191,226,82,86,154,1,264,141,87,171,78,30,492,12,18,723,152,119,109,240,11,354,447,23,366,84,114,22,91,323,65,45,326,20,110,106,32,228,253,128,279,148,116,24,106,134,196,60,33,35,202,879,27,38,46,78,66,32,84,88,60,78,71,5,227,105,23,211,318,48,432,168,62,4,38,71,305,6,330,570,56,120,17,103,72,412,20,8,20,72,13,97,27,256,51,594,116,102,34,107,4,151,85,207,93,40,149,450,198,131,73,46,173,63,280,90,146,228,10,67,28,405,106,26,2,81,149,152,71,107,57,4,121,23,413,12,268,147,31,410,112,198,30,51,160,11,77,127,117,99,34,159,9,99,32,44,23,229,31,148,216,108,29,199,185,129,198,9,73,48,78,269,147,358,50,82,44,148,4,111,28,68,180,628,61,80,96,126,593,1,760,14,396,229,21,18,129,12,461,178,20,66,144,472,227,51,118,87,45,47,13,158,62,79,69,562,66,72,38,185,28,193,107,21,210,120,108,490,38,24,70,92,92,178,33,20,35,20,102,186,24,36,502,2,166,311,139,90,30,72,950,18,8,254,124,256,132,367,508,40,33,22,170,166,84,8,113,427,340,325,217,48,190,356,24,270,156,44,7,7,578,46,32,5,77,78,50,11,35,66,8,16,14,281,201,74,70,20,143,109,12,42,14,34,129,41,372,16,38,334,7,235,54,96,256,84,96,34,128,37,216,51,21,432,85,18,162,244,67,13,114,284,188,98,63,155,68,44,58,107,103,97,137,207,477,87,99,168,61,557,12,8,508,76,35,275,16,104,40,206,34,374,4,12,66,85,7,180,136,170,240,36,131,67,249,129,10,92,90,100,272,34,56,57,5,176,20,646,5,51,57,39,29,43,6,174,12,100,110,84,342,12,276,37,107,282,420,24,87,49,288,38,10,344,126,70,132,8,34,110,4,440,42,130,46,81,288,235,117,81,163,60,489,234,36,48,366,6,108,80,324,6,120,347,108,185,590,30,182,10,30,100,49,5,26,206,46,61,47,77,181,90,65,5,30,84,342,324,203,51,42,120,244,60,126,180,128,10,8,70,260,54,66,130,171,11,16,34,116,182,53,31,40,14,174,213,77,46,12,17,581,42,97,275,145,216,111,369,349,22,20,5,131,452,6,274,38,178,296,196,73,95,101,189,235,129,230,1206,100,436,194,460,122,283,169,478,9,59,149,53,8,70,54,7,59,45,59,5,163,138,64,52,116,198,37,73,35,181,234,82,50,64,120,194,70,12,60,228,282,110,202,122,70,158,318,34,101,87,130,68,144,487,203,10,138,32,58,23,21,268,22,38,80,58,60,120,30,10,109,384,12,205,558,253,124,24,97,178,46,232,266,142,99,27,42,360,356,18,106,256,388,327,111,133,27,25,73,18,120,100,110,283,295,278,210,50,148,290,18,384,36,82,218,312,16,144,362,150,123,61,282,145,7,36,561,88,131,225,292,89,203,287,38,34,52,256,100,296,206,26,492,48,5,57,48,22,13,101,126,78,59,193,38,17,43,74,188,44,150,12,13,159,93,443,22,222,162,150,170,138,58,14,124,42,95,4,16,52,165,38,88,245,153,58,76,8,70,51,40,13,106,66,24,102,169,95,137,33,186,12,160,65,33,18,5,91,60,30,124,324,56,166,228,297,280,53,8,100,415,13,30,142,90,221,28,7,584,84,308,125,245,132,46,58,112,74,6,47,133,112,48,204,234,33,107,544,6,104,228,18,70,55,7,72,18,10,54,78,98,124,19,4,283,358,176,116,40,44,6,30,72,108,30,301,89,423,716,13,10,30,110,226,446,226,264,59,69,240,40,276,115,91,161,43,60,150,364,170,70,38,121,299,42,12,240,387,31,21,209,190,108,300,182,76,107,49,24,354,433,103,94,1787,169,204,62,64,50,67,717,138,108,300,512,18,40,298,26,126,192,25,5,90,122,66,160,26,324,16,26,49,159,134,60,156,63,196,45,116,112,122,42,4,36,50,25,215,66,178,126,56,252,28,138,62,52,162,6,71,7,494,70,97,203,245,37,126,12,190,2,36,42,11,31,116,52,66,48,72,132,103,47,378,26,18,198,52,124,146,343,115,60,28,72,282,20,267,55,86,39,192,139,258,96,123,388,109,216,24,32,154,220,114,114,261,45,156,92,12,414,101,11,24,80,154,246,48,29,92,61,358,222,240,55,49,232,387,24,83,94,216,84,42,384,56,266,178,6,271,533,15,1,32,576,684,42,70,306,198,236,152,658,141,68,483,56,177,4,221,78,42,228,216,96,43,43,165,89,108,3,137,135,81,156,110,24,60,76,240,176,112,246,102,20,70,226,566,42,48,38,86,388,88,62,78,377,357,388,88,135,148,100,13,176,328,132,36,231,187,77,15,30,72,192,296,190,8,21,43,261,107,162,22,98,96,175,316,5,14,22,80,28,2,294,18,108,72,510,22,13,17,264,50,152,140,324,74,59,13,22,116,10,26,486,179,169,34,36,546,30,168,16,32,152,22,19,29,18,80,352,68,21,57,34,468,38,844,404,28,68,11,205,6,6,184,210,6,164,180,154,541,91,108,112,30,230,113,331,76,168,42,44,291,217,456,186,14,220,19,13,28,224,100,128,54,510,160,116,258,154,50,246,52,72,222,21,56,129,31,333,146,89,311,33,315,12,52,58,18,32,1,123,298,606,16,104,50,64,151,299,68,60,4,210,20,16,138,6,66,284,238,26,425,37,222,168,112,85,100,123,44,129,376,81,138,16,61,77,43,13,38,206,2,89,88,13,30,216,80,180,525,5,400,112,23,93,114,58,259,221,140,534,341,35,457,95,34,236,12,30,44,272,58,191,48,143,158,63,357,42,112,288,54,43,67,96,724,294,123,8,273,123,373,7,185,44,136,222,121,145,102,252,220,181,251,14,303,8,95,144,186,44,12,267,141,84,43,75,48,120,54,428,78,256,200,5,125,75,268,152,41,340,198,9,40,47,66,48,542,28,164,46,51,23,42,208,38,150,84,76,240,642,338,82,249,77,46,1,421,112,2,252,160,8,600,48,100,246,38,342,70,84,25,256,225,906,42,16,72,70,2,186,146,54,742,452,6,94,7,31,201,3,220,54,191,169,74,58,222,494,72,52,50,574,227,7,201,45,80,160,23,291,84,38,68,222,68,124,158,244,314,214,66,576,26,51,7,180,486,200,180,6,90,83,12,35,145,72,164,47,106,80,784,114,128,204,126,322,62,335,29,203,111,61,17,288,36,426,100,44,16,194,314,74,218,172,20,156,6,11,457,10,146,103,228,244,19,172,168,192,241,164,149,74,109,261,259,172,5,31,1,84,6,420,322,20,96,130,174,175,265,58,108,396,36,109,189,66,166,174,161,125,78,216,220,534,20,140,114,52,68,48,22,36,39,88,5,78,350,556,147,171,266,43,3,14,10,164,112,98,11,115,126,178,246,104,14,122,159,245,132,36,304,140,7,101,238,12,30,236,82,470,382,85,55,464,184,60,21,53,520,11,280,327,456,9,4,119,400,94,38,506,94,193,73,36,220,90,104,12,77,285,76,126,60,25,401,120,78,6,138,62,58,74,74,204,60,368,49,389,184,20,127,192,141,18,120,38,172,2,40,114,56,78,310,78,24,330,50,334,67,295,146,702,18,24,263,155,1,21,44,136,60,120,42,188,222,156,94,42,8,207,85,95,219,190,20,139,53,271,131,169,20,287,140,144,69,164,48,9,63,19,173,128,296,448,35,96,104,148,80,42,60,124,410,66,6,70,80,214,194,8,3,139,124,648,49,80,481,50,533,36,309,287,60,115,12,101,524,113,112,308,52,8,96,118,69,161,10,68,180,82,56,95,65,60,122,208,314,36,180,27,135,18,23,384,23,174,134,90,180,150,125,95,72,2,11,9,40,48,24,40,144,32,310,17,117,76,24,59,84,315,6,24,126,33,8,143,328,22,126,100,6,30,49,47,205,31,24,585,32,9,146,140,508,109,28,181,264,62,48,150,438,204,136,54,96,18,12,128,41,89,350,84,110,427,195,32,21,241,142,102,12,87,59,437,53,150,12,290,186,162,22,25,25,90,53,263,144,26,40,139,108,323,72,46,28,183,643,198,20,24,18,82,80,126,14,248,2,138,34,249,39,18,127,53,134,268,6,12,134,1,69,75,411,106,206,9,303,82,116,126,469,5,350,6,52,18,144,4,74,263,171,16,62,206,314,128,78,29,61,270,126,46,78,434,36,366,166,114,148,207,248,41,102,330,160,95,55,194,46,198,303,33,266,293,205,40,122,102,231,211,128,328,141,81,308,3,25,84,90,50,28,18,6,248,222,133,256,65,135,17,72,315,147,41,35,141,131,12,106,2,77,413,30,110,6,24,436,106,206,650,132,48,10,120,320,82,342,50,198,212,46,370,405,20,67,420,274,63,24,241,348,352,56,160,7,104,41,228,42,132,161,307,165,27,1,159,100,76,234,75,351,144,40,78,32,70,54,24,119,237,3,33,186,24,10,24,2,65,103,64,9,59,58,92,155,128,471,98,118,2,127,351,180,16,145,116,205,6,125,17,138,24,21,40,77,2,6,71,131,42,78,98,12,60,184,79,47,102,36,336,144,500,52,284,238,61,91,4,144,488,348,158,279,103,190,14,52,26,299,125,26,377,193,172,179,351,186,64,186,42,104,204,370,102,98,80,316,208,353,79,164,172,1164,22,420,538,70,8,35,7,6,474,4,2,274,176,54,78,210,75,4,47,461,23,206,499,45,3,219,284,276,184,174,132,256,214,37,647,94,36,104,76,7,85,151,87,33,207,66,20,4,284,44,28,36,42,12,318,16,182,12,90,180,42,185,55,274,200,84,126,30,76,60,56,27,15,88,277,175,66,4,246,6,24,176,408,55,33,152,378,10,354,45,165,20,23,287,84,200,106,356,72,238,78,14,160,222,198,122,94,32,13,147,234,8,35,72,119,25,397,34,708,56,34,67,175,66,252,180,22,90,79,55,790,55,37,340,98,36,144,126,256,71,48,75,240,150,150,56,180,121,133,146,54,166,37,311,49,373,114,118,124,3,31,48,336,154,152,112,228,132,32,23,131,60,360,64,230,296,232,30,37,239,229,25,108,63,169,158,34,427,251,120,32,16,9,63,54,44,24,102,29,131,120,120,96,221,579,141,157,60,92,30,353,125,28,94,100,80,113,61,220,374,8,38,266,94,18,126,272,102,228,340,212,129,91,72,4,177,119,6,84,194,144,52,89,25,120,166,230,191,39,168,109,12,120,152,68,25,34,5,21,70,60,5,9,46,122,84,294,34,96,26,124,293,32,29,30,68,112,12,174,148,80,48,174,229,71,6,20,366,28,20,394,162,30,348,26,14,362,8,108,108,186,6,1,213,572,56,430,406,42,240,100,302,274,316,120,73,149,174,69,31,56,28,168,8,184,225,109,238,73,81,296,76,43,19,125,31,156,24,160,140,10,312,68,47,385,99,52,9,20,80,8,50,153,48,15,400,254,132,72,18,24,10,18,150,68,252,30,610,50,21,23,146,162,164,70,58,28,604,41,111,29,44,540,8,343,477,371,226,140,296,158,50,126,65,301,176,100,10,20,288,336,29,59,13,144,161,7,155,62,130,5,103,445,91,218,206,68,465,85,199,85,120,59,167,173,61,474,241,89,282,20,56,182,156,171,15,30,204,206,72,316,20,54,28,16,212,98,186,386,60,82,264,147,39,640,282,318,173,219,198,184,80,34,14,12,70,206,171,87,52,68,42,162,118,247,431,2,52,12,8,48,187,111,260,142,120,19,56,29,166,32,42,10,270,54,152,372,12,298,6,33,167,136,378,211,7,204,96,5,133,63,63,204,8,14,54,108,517,223,12,86,8,36,251,191,94,58,20,461,52,111,46,366,68,12,108,129,217,132,68,276,34,162,200,322,90,91,161,15,320,75,18,198,130,128,12,47,73,298,42,30,106,142,273,51,205,51,90,171,3,133,23,46,203,52,31,322,122,184,72,68,160,165,87,521,93,46,174,8,8,104,60,223,80,100,37,31,167,165,43,8,42,4,144,35,189,28,362,162,198,12,90,143,197}; int t2[6230]={533,305,367,141,69,30,118,2,77,84,109,150,201,129,123,104,449,11,332,67,52,413,43,124,9,317,540,46,146,6,22,72,126,145,151,125,297,327,23,109,117,15,136,53,4,35,199,61,385,220,112,267,817,219,1232,16,205,284,436,31,159,61,96,128,324,208,157,646,372,84,406,460,171,3,36,5,55,25,88,21,138,201,231,36,178,979,49,52,67,28,99,250,218,70,83,15,108,89,107,53,125,67,300,60,149,252,31,275,300,128,41,251,136,118,307,21,19,269,70,41,363,96,68,161,81,84,411,347,93,196,240,140,173,36,203,85,68,167,477,194,77,32,325,95,549,56,126,36,181,81,31,205,76,266,36,86,188,470,80,21,245,14,414,19,109,234,272,193,485,88,410,90,199,127,24,289,40,68,571,21,21,18,69,143,297,204,41,11,187,77,7,6,266,358,251,21,84,95,89,22,84,282,244,11,364,93,76,55,175,4,246,80,30,68,182,6,80,129,25,864,163,40,13,59,193,59,440,45,102,109,84,248,12,57,52,106,184,14,156,96,355,364,77,96,460,24,143,77,26,396,156,108,150,86,410,544,63,119,26,235,395,10,212,142,52,205,49,139,36,199,72,485,520,373,4,760,82,278,98,337,397,38,86,56,518,137,1,279,203,202,111,67,13,175,28,301,244,12,32,285,1095,23,5,219,89,299,113,423,82,90,28,60,490,295,163,61,195,93,24,169,42,5,404,67,33,79,153,116,128,213,26,1,12,157,8,87,76,131,52,286,62,41,35,94,346,266,855,65,278,274,143,61,439,33,307,56,99,105,31,156,86,158,2,76,288,575,20,81,160,51,243,112,77,336,120,289,28,51,13,131,96,513,63,27,38,11,164,244,75,550,376,102,88,324,48,72,304,53,109,10,134,35,392,112,380,300,71,301,57,56,344,211,16,64,285,735,25,427,24,156,16,752,28,19,130,195,53,390,65,131,489,96,93,160,83,55,69,224,388,219,70,6,233,49,348,138,65,12,127,14,68,8,142,256,165,7,6,407,140,83,421,264,337,540,56,351,928,111,33,81,47,305,404,482,697,251,1,119,72,49,140,148,139,120,485,200,303,8,104,33,39,69,313,162,553,24,228,275,12,96,161,65,195,11,252,12,94,67,344,5,234,156,288,10,156,302,85,347,25,287,756,50,142,65,1368,84,95,108,148,380,33,499,160,90,162,30,59,57,59,59,85,84,400,35,13,213,139,417,270,140,302,127,236,15,72,72,460,5,76,507,77,161,60,152,144,395,27,176,240,148,166,263,73,18,268,38,203,112,357,323,280,271,72,353,656,109,75,56,11,98,62,158,96,36,223,41,36,116,71,169,186,113,351,125,352,160,56,179,97,60,4,560,24,101,35,497,127,81,111,92,33,67,301,384,72,143,891,57,39,345,44,213,204,22,77,241,22,205,160,105,58,296,69,500,952,68,287,233,243,34,34,261,347,216,757,197,119,33,170,8,421,173,12,275,165,63,61,472,3,300,160,875,254,139,155,605,96,56,249,259,668,208,104,168,497,14,442,155,20,71,53,188,4,65,200,18,73,147,152,65,85,120,50,89,333,7,113,102,109,68,111,189,12,173,7,48,127,344,122,278,44,397,140,85,3,69,15,236,91,110,31,72,147,170,159,144,196,120,77,3,167,53,343,40,162,50,124,133,81,75,72,95,256,66,36,16,230,32,422,91,436,4,279,28,417,40,85,330,20,29,17,260,39,149,80,270,65,252,36,48,452,244,144,19,760,157,139,132,30,58,277,76,55,402,58,132,38,94,9,147,194,415,7,206,15,92,72,88,368,191,286,135,204,55,165,48,236,63,321,208,136,16,117,144,231,23,34,102,80,488,416,50,220,60,135,9,28,234,5,120,24,532,297,12,318,37,340,68,153,2,180,48,424,332,58,26,176,49,36,205,139,9,130,389,49,119,51,57,7,146,202,100,6,50,560,124,332,97,56,201,55,269,884,90,120,36,96,30,6,8,89,77,204,156,142,288,21,372,227,185,285,2,69,27,30,212,259,129,274,449,112,36,91,92,24,328,209,51,78,58,358,454,50,52,227,673,47,335,16,98,20,99,92,120,245,316,44,407,72,237,47,157,123,27,332,13,44,249,495,165,404,66,200,38,7,36,80,36,167,164,592,432,49,19,305,180,41,95,155,4,125,12,312,501,15,211,129,92,48,149,95,73,35,225,138,440,130,12,375,139,161,3,9,7,46,254,125,25,448,3,209,115,209,31,96,207,480,573,4,236,197,552,19,85,278,374,56,51,11,582,92,527,9,244,118,2,86,201,104,33,444,75,80,128,131,290,46,62,44,224,212,14,20,114,967,312,391,344,62,428,175,512,69,352,170,73,48,220,216,9,40,504,326,138,54,66,210,257,137,95,192,176,312,28,105,234,152,165,76,73,38,298,52,90,177,47,49,59,245,97,107,189,147,300,33,26,206,66,688,234,183,161,112,58,1,39,28,14,35,8,352,67,232,204,218,480,296,210,430,698,773,103,657,84,128,276,84,219,220,234,142,13,165,92,38,18,35,45,27,52,41,14,9,32,293,194,56,114,179,144,369,142,4,174,175,131,200,17,123,236,36,74,3,57,250,269,427,18,60,227,24,73,8,298,216,169,29,31,151,201,27,213,468,504,36,12,44,193,42,4,149,32,24,93,38,288,17,117,36,42,33,67,66,294,86,340,47,36,377,14,94,487,408,445,54,62,367,92,164,1,27,152,215,160,18,343,19,281,59,4,126,182,72,236,46,51,244,192,19,60,73,665,367,221,143,176,67,32,88,93,165,23,25,90,112,144,68,434,43,36,24,56,131,434,43,340,48,381,15,201,67,128,45,94,21,543,309,164,371,5,84,20,84,13,36,148,216,172,231,261,199,33,179,340,13,218,101,3,18,168,26,126,20,344,30,277,108,4,121,643,261,46,18,83,215,402,147,271,105,541,139,40,349,11,684,32,579,97,57,27,99,606,420,34,205,63,541,573,112,2,81,23,214,228,958,65,756,9,264,58,198,488,175,57,67,192,132,131,56,413,144,67,130,60,84,978,85,609,548,211,17,344,264,347,120,232,87,66,131,432,35,50,63,175,689,363,148,197,307,74,102,386,126,32,245,396,12,265,206,68,265,25,191,72,55,4,9,148,203,324,184,138,3,37,175,51,44,38,59,253,114,180,101,5,163,12,67,8,253,32,112,24,15,120,154,155,73,46,364,36,80,141,432,247,161,132,35,24,164,113,184,15,32,133,87,46,68,159,116,37,478,130,156,7,740,225,26,126,163,71,34,60,259,127,112,124,88,54,574,9,364,139,38,134,38,71,140,103,30,76,30,5,55,156,232,56,637,323,138,16,6,97,104,29,240,623,224,159,1,8,393,43,91,2,279,29,334,81,488,199,46,150,216,118,728,678,164,8,429,295,401,575,401,125,112,291,189,76,35,1,180,163,69,498,453,28,71,537,55,16,228,133,472,288,75,149,81,374,90,2,77,4,260,9,184,279,456,25,408,299,56,25,267,19,86,130,18,234,125,408,320,19,34,34,754,18,26,242,128,58,66,744,54,415,80,8,3,69,636,61,456,287,3,5,48,701,10,45,129,14,228,493,304,252,20,147,201,348,213,115,4,229,231,160,75,556,52,450,354,225,149,76,72,84,327,271,117,584,120,143,13,201,2,132,264,85,21,519,272,9,252,210,85,69,351,48,84,84,133,50,226,420,350,28,52,180,161,91,306,247,351,97,168,187,552,193,168,52,97,155,389,51,125,260,19,584,59,106,154,4,84,73,128,111,234,427,225,7,380,37,58,158,474,118,255,323,202,211,252,11,70,68,110,113,68,35,56,116,78,39,216,93,206,149,396,360,120,119,4,161,123,332,110,224,530,881,552,385,35,12,65,218,93,7,226,62,92,37,72,901,359,313,35,283,89,21,63,160,80,180,16,55,53,73,112,204,122,70,211,156,972,583,257,92,108,63,57,61,59,69,331,228,128,384,52,151,228,161,532,613,18,121,36,56,784,44,60,123,248,29,44,83,8,192,57,15,141,525,12,36,442,302,422,68,210,20,219,145,48,91,167,125,201,131,9,236,163,52,269,147,439,72,221,64,625,164,8,222,210,39,219,38,324,67,628,144,91,406,651,220,185,48,164,214,33,384,81,15,124,44,69,7,9,671,3,130,112,538,961,25,287,164,97,2,12,232,58,112,150,9,335,337,465,3,315,24,73,92,397,224,158,630,232,72,38,5,60,72,241,394,25,31,6,43,489,116,203,153,78,273,169,6,41,7,60,1,11,344,89,55,5,503,629,191,289,117,398,69,433,90,216,113,1,248,79,12,180,32,129,8,131,325,224,3,23,189,616,60,103,130,14,245,20,11,106,164,200,30,125,324,131,481,24,72,160,375,310,22,278,47,189,11,136,27,92,236,226,42,36,25,389,30,1,357,299,172,309,255,24,121,11,48,117,36,18,4,26,190,74,6,129,60,29,375,49,27,41,60,104,22,16,166,131,175,12,16,21,48,231,44,110,59,7,48,48,114,203,41,47,43,198,175,131,121,391,36,82,152,147,293,242,41,296,53,150,157,168,117,24,535,24,123,36,58,162,41,409,380,75,80,19,4,80,513,620,167,222,491,117,40,38,17,15,128,268,730,347,45,139,69,22,52,25,269,331,8,72,304,176,31,36,77,208,156,157,43,35,174,78,353,81,456,219,309,120,218,90,74,312,73,243,114,290,53,69,56,74,652,57,65,210,25,161,4,55,67,342,39,287,101,196,3,22,7,460,31,62,90,296,177,55,22,158,182,164,24,12,67,5,556,276,660,66,196,333,285,23,148,5,966,138,196,56,46,165,113,308,20,176,276,463,284,208,20,328,27,8,37,97,152,111,15,158,572,72,206,89,373,435,49,186,49,93,55,73,50,168,100,17,63,394,283,115,422,2,280,230,211,84,15,26,427,39,157,319,48,77,303,189,251,529,80,57,163,188,23,53,24,391,17,192,25,76,54,50,11,236,149,38,34,74,302,30,174,463,131,129,13,12,76,56,183,176,64,84,31,246,163,23,145,324,40,83,13,603,57,227,176,305,97,94,312,1,97,172,39,215,132,73,215,5,21,78,9,229,82,45,143,94,124,368,271,164,125,314,316,341,115,41,12,69,563,16,185,62,198,114,48,125,192,40,284,333,143,36,33,48,271,25,107,343,70,128,4,423,93,127,1,116,35,216,135,13,265,71,119,64,101,319,144,33,151,56,344,37,183,700,165,96,224,84,275,10,839,35,337,24,24,64,168,41,27,292,339,189,363,213,45,60,135,377,150,266,219,267,25,360,280,47,249,247,197,55,89,143,77,101,176,115,81,70,105,97,182,160,202,250,252,185,119,4,289,19,116,37,77,139,55,109,97,31,688,3,50,18,73,299,310,328,48,448,490,94,56,120,3,195,130,67,124,68,67,12,390,99,108,145,172,58,29,41,311,363,284,108,108,345,19,9,23,254,108,94,4,57,32,220,48,169,91,40,60,392,36,121,219,33,18,74,87,379,29,375,121,29,102,145,32,343,56,14,143,83,120,8,4,86,115,11,13,41,208,127,168,1,24,282,544,2,104,24,16,50,34,115,97,156,55,79,364,220,200,153,41,259,72,84,27,429,169,176,35,15,345,109,287,209,26,181,21,151,125,71,121,143,79,173,60,44,64,296,711,40,358,26,302,252,19,97,43,48,33,272,199,31,65,64,165,63,108,341,48,192,66,165,259,201,91,109,109,34,136,370,64,254,140,153,143,226,88,108,135,235,77,44,5,562,85,104,64,264,408,457,7,21,106,76,85,108,244,56,65,343,60,12,280,308,95,16,522,40,71,180,72,180,161,60,38,21,140,155,13,396,311,565,135,145,19,186,98,14,68,178,337,176,855,122,67,131,320,58,64,295,91,276,138,1007,263,301,67,144,181,285,19,1,47,132,104,45,100,4,83,16,148,579,92,106,56,6,41,171,533,12,17,318,85,52,288,8,16,179,577,57,148,19,40,456,188,71,185,49,306,30,91,229,108,114,166,102,82,368,4,191,219,97,109,111,92,40,135,164,421,20,215,6,36,391,244,3,185,365,180,110,136,65,99,12,65,83,96,265,1069,15,669,123,297,27,347,228,194,344,106,256,140,194,86,654,4,111,116,40,55,269,36,55,817,304,116,335,58,19,161,296,94,48,33,147,692,5,16,107,150,30,196,126,7,111,141,189,18,154,155,136,116,43,262,12,978,256,318,271,128,85,140,79,351,56,249,172,821,56,116,196,232,130,510,219,163,6,144,106,349,36,36,27,125,143,54,83,351,449,363,4,168,138,124,143,156,109,16,126,138,31,93,216,144,290,6,315,53,343,129,252,68,50,22,19,52,73,307,215,570,238,141,237,562,224,141,5,199,1,35,141,355,137,210,114,15,31,72,74,43,723,29,172,51,176,1,67,245,236,148,325,226,6,463,39,328,217,112,68,201,18,10,306,345,5,115,675,161,85,182,20,73,177,99,143,313,45,235,136,81,104,299,324,88,161,115,169,83,131,212,26,35,7,224,220,61,428,213,315,37,35,404,253,172,91,59,2,207,92,53,235,25,71,243,249,243,470,66,180,5,131,170,679,7,66,202,284,629,23,170,26,109,25,164,131,100,111,298,20,286,50,107,259,222,34,194,12,54,53,129,44,71,89,94,65,15,442,32,18,230,54,389,168,177,112,6,37,376,140,64,13,55,91,17,141,402,117,33,123,136,9,136,707,39,33,147,208,89,159,353,157,27,144,7,52,442,39,1,38,16,148,30,3,295,46,72,95,320,23,38,734,94,496,56,12,143,109,256,331,744,20,344,93,42,176,165,21,43,69,119,4,139,88,28,154,52,14,181,293,347,80,468,133,147,113,63,288,19,233,123,177,87,152,77,7,521,95,97,164,221,43,45,19,212,240,24,196,19,169,41,324,376,72,139,24,115,216,161,189,180,159,116,16,41,22,50,284,134,18,111,188,12,112,55,38,20,96,194,22,59,52,4,37,83,48,459,33,29,87,352,284,96,85,23,636,59,44,54,8,379,84,97,146,29,400,156,140,91,201,273,287,5,90,156,54,306,257,11,94,70,50,275,179,260,341,165,122,341,139,97,168,79,20,381,580,321,35,19,80,177,23,188,250,8,74,64,237,92,3,645,137,207,436,376,69,38,109,33,444,3,851,156,242,4,164,355,77,151,72,104,7,34,195,25,34,26,178,30,75,160,125,163,53,155,664,28,199,34,31,115,2,124,11,69,124,124,488,58,114,54,45,4,516,5,42,188,62,60,12,72,48,71,12,73,596,18,374,8,90,42,66,54,206,765,127,93,260,136,97,175,108,545,7,108,292,4,167,248,73,19,37,121,179,40,204,285,632,28,243,181,47,51,53,3,2,100,63,228,95,76,74,208,48,271,83,298,47,28,65,280,207,8,51,93,132,225,20,235,217,39,108,31,184,157,223,41,149,727,359,93,155,108,53,36,147,149,100,672,235,101,180,187,28,134,135,149,304,98,2,378,225,89,62,68,61,399,172,13,72,332,88,244,19,73,201,172,72,135,264,180,236,100,140,7,40,110,412,40,326,53,44,155,12,126,227,369,783,31,5,97,35,95,58,10,24,28,33,231,480,177,43,52,304,186,122,84,20,60,44,148,233,13,183,228,272,83,1,67,341,28,143,457,69,92,39,352,632,24,156,156,208,189,383,255,150,96,30,564,64,461,117,4,34,17,351,269,23,188,100,324,46,19,607,173,57,538,60,48,65,51,46,331,45,80,587,8,151,2,82,484,36,181,541,118,424,33,53,611,101,163,164,132,155,209,44,341,131,336,55,81,63,13,883,624,180,150,244,19,83,205,91,136,73,57,115,17,63,228,239,144,261,376,7,93,68,131,5,175,32,20,34,258,45,140,65,62,8,134,48,16,179,148,40,109,198,182,88,316,56,6,2,70,68,66,444,6,192,136,42,172,92,271,9,159,497,35,60,227,174,154,330,320,15,264,189,230,148,376,9,252,156,28,164,223,30,115,139,5,136,69,210,568,269,188,100,612,197,270,44,149,221,84,108,51,179,113,175,145,63,28,322,191,599,344,153,272,180,127,169,243,13,68,143,54,623,57,35,684,89,14,134,20,124,175,36,19,204,70,66,73,89,156,34,286,43,163,48,21,177,204,96,16,115,213,87,113,66,54,55,239,12,313,249,46,246,144,435,228,323,141,7,453,171,124,4,141,41,408,4,86,41,31,137,308,81,362,490,14,12,404,18,59,947,208,213,65,398,28,36,26,20,8,366,12,17,137,259,221,454,64,24,174,7,13,42,106,236,159,8,129,154,101,99,122,88,222,121,1,367,227,5,47,430,420,323,108,103,317,16,24,308,48,3,56,168,176,88,54,79,183,8,72,5,64,76,35,85,52,485,28,216,423,139,245,303,117,161,83,107,213,12,20,355,88,614,3,483,256,156,53,37,82,392,197,117,464,111,312,651,50,56,20,211,279,748,60,245,199,324,14,110,90,163,48,85,120,242,62,74,4,268,128,128,1110,22,33,172,48,164,71,17,12,180,3,257,43,326,66,201,297,367,92,609,14,648,648,101,80,27,13,80,316,104,136,313,30,49,100,9,128,26,269,31,64,13,8,33,144,252,222,26,295,43,249,93,75,132,200,196,45,220,7,9,79,27,178,42,157,593,286,1,228,29,2,77,165,102,461,77,72,11,61,144,216,19,295,285,252,488,40,389,328,184,112,183,87,201,13,94,65,320,41,18,90,7,13,76,82,453,85,119,40,63,52,98,164,210,216,126,235,375,533,292,101,91,248,461,155,33,119,135,198,111,131,130,36,63,343,58,55,264,136,60,25,142,290,256,55,164,100,99,52,38,83,36,48,81,194,29,20,132,203,34,111,177,55,440,216,313,128,43,175,22,150,30,87,531,201,61,24,554,229,120,91,13,168,89,299,7,140,40,258,119,200,27,64,160,118,7,69,12,192,167,43,300,72,100,20,17,24,100,109,87,127,118,12,88,24,23,192,156,132,20,496,187,30,103,93,63,96,527,168,145,53,98,154,227,300,99,21,20,17,68,142,161,201,182,86,59,200,179,158,119,16,17,4,39,115,18,28,687,363,193,48,175,97,64,119,406,435,12,8,41,46,32,156,62,170,74,190,45,67,316,40,93,48,84,88,311,217,344,35,37,20,159,89,85,44,62,69,87,136,52,121,444,53,102,60,732,353,9,483,5,74,14,95,3,613,20,84,411,236,237,208,79,70,16,339,195,129,15,25,60,108,7,193,144,41,7,35,41,180,67,17,140,341,204,62,84,8,69,412,337,190,105,181,27,59,157,24,120,116,209,48,199,36,727,302,199,91,1,48,120,527,46,60,394,182,64,107,84,116,44,123,17,112,420,135,28,197,3,170,124,172,36,272,47,316,61,55,124,55,241,349,56,15,51,222,79,175,10,207,193,152,10,280,194,398,14,58,30,44,90,12,32,298,358,45,11,1,115,14,48,51,448,204,663,45,68,379,45,25,872,11,160,75,268,185,29,380,182,226,343,665,299,295,194,22,204,120,301,39,201,48,239,60,85,44,59,122,15,21,348,303,41,28,112,327,433,180,76,39,327,33,384,196,373,47,228,161,176,514,210,259,417,39,45,64,8,442,329,63,173,33,31,485,120,76,132,287,180,156,105,139,337,32,372,155,172,360,228,7,33,75,540,385,132,167,37,67,316,62,275,100,56,168,60,52,443,80,28,44,81,111,77,156,379,85,99,284,42,424,44,2,450,140,235,380,40,49,71,224,336,79,117,73,91,155,8,281,33,60,100,3,271,50,22,61,105,99,48,312,211,57,427,20,172,10,379,16,64,153,51,341,178,86,94,193,128,3,101,81,487,193,166,174,43,45,75,59,62,143,392,101,264,59,204,201,134,20,414,231,276,200,159,9,460,243,21,64,164,337,102,60,152,149,233,24,103,99,8,36,38,106,97,83,445,109,274,72,37,779,77,25,266,136,41,264,228,19,209,385,55,144,292,84,691,113,175,30,47,165,471,720,381,295,412,240,47,10,4,75,24,113,60,199,57,204,183,215,325,236,144,39,1,13,35,308,181,99,8,257,187,211,250,112,123,63,60,73,20,144,215,66,96,139,87,204,57,348,5,178,260,414,11,97,115,37,516,20,62,65,43,209,219,80,22,251,340,75,9,101,6,28,441,429,195,140,305,282,25,168,52,68,33,248,82,93,65,79,317,184,410,18,83,20,172,184,129,56,270,141,181,127,3,249,5,34,369,192,57,210,72,21,88,47,33,204,653,26,1,673,255,16,91,264,114,20,212,148,106,80,5,244,133,224,11,27,116,49,23,222,310,117,161,235,127,33,348,135,2,388,106,413,181,71,116,205,83,59,6,10,237,7,125,247,36,62,795,232,139,161,348,9,147,175,40,88,138,123,72,288,111,9,73,239,133,847,216,420,7,413,189,10,4,270,35,197,243,57,152,36,42,16,54,76,71,405,170,1020,333,7,97,451,157,17,235,64,32,21,4,446,133,83,313,401,103,305,398,218,92,146,157,53,80,190,80,824,6,91,300,45,99,300,216,224,4,187,152,146,122,188,238,18,404,33,343,134,135,56,180,81,188,162,89,251,318,51,3,46,136,87,461,99,428,515,22,280,27,36,320,183,86,30,218,275,52,257,36,108,50,658,220,142,89,135,8,62,2,93,95,38,83,153,347,125,130,396,13,56,132,200,181,26,246,91,193,23,351,141,9,48,451,224,136,7,53,41,291,48,167,98,30,156,18,18,233,504,213,3,40,3,100,5,233,198,621,57,146,6,138,72,16,38,106,566,127,71,170,27,225,27,96,35,654,148,4,288,151,292,411,318,354,144,102,58,308,194,15,20,183,14,68,112,44,196,119,51,280,34,16,343,23,334,63,373,187,96,275,85,81,166,136,349,731,236,54,96,900,124,126,328,1,135,52,269,115,89,217,19,136,163,328,33,71,114,55,24,51,26,19,40,60,180,47,46,226,128,218,78,80,37,160,181,90,30,72,268,48,99,276,29,43,87,180,81,329,42,10,74,89,129,71,1,11,5,90,22,2,29,25,211,132,108,395,180,210,119,20,169,251,73,198,197,73,52,342,540,162,19,120,213,40,2,236,13,367,36,2,92,23,13,95,963,29,43,425,144,216,27,1,116,92,16,28,24,121,227,376,76,161,24,26,213,41,192,22,137,49,160,232,56,55,45,63,205,548,130,200,272,81,113,51,41,291,71,668,140,441,65,35,8,75,102,458,85,87,188,209,320,37,111,48,80,388,11,72,93,185,48,511,91,29,35,124,97,387,17,55,17,112,115,301,52,97,18,265,244,31,182,18,84,146,164,22,153,180,35,5,428,25,19,233,16,120,82,57,39,25,332,47,98,112,72,304,42,112,221,40,180,236,395,569,12,71,10,243,20,307,314,8,486,9,237,198,37,207,25,43,144,265,21,118,9,127,713,1,124,200,463,65,34,241,185,152,43,381,3,88,239,66,18,2,91,89,11,29,144,406,28,90,119,236,84,340,175,109,13,411,132,165,46,64,229,31,188,5,101,47,324,73,527,128,11,217,513,255,185,95,219,196,397,339,21,388,23,433,53,88,192,208,84,62,226,80,27,116,195,13,7,553,132,31,158,98,130,390,121,3,281,139,28,212,60,8,158,20,335,171,96,33,40,12,80,71,62,35,71,205,36,175,340,178,2,38,287,216,280,127,97,125,286,70,20,627,28,212,9,99,60,235,449,36,192,363,129,87,158,311,12,67,344,133,176,247,78,227,77,151,141,47,12,23,265,115,116,9,160,55,89,237,39,197,210,6,15,283,32,80,24,86,362,14,43,503,49,161,411,152,60,20,111,33,95,361,59,161,49,131,355,70,290,6,79,73,28,20,131,75,166,4,43,421,83,83,158,156,779,41,174,217,201,718,101,112,72,96,75,48,129,48,73,271,75,102,67,57,254,350,43,439,210,208,148,166,285,29,482,136,12,205,89,368,130,20,8,45,121,44,8,79,103,173,89,319,164,107,149,247,252,112,84,645,64,223,125,441,107,79,62,140,391,83,326,30,153,43,136,237,483,28,189,512,5,90,17,80,81,39,125,71,12,44,384,24,259,164,180,33,76,140,3,5,107,1090,10,8,254,279,23,37,132,97,60,155,35,49,204,189,159,12,272,196,332,43,198,335,13,410,237,196,1,190,256,89,1,159,29,15,157,39,261,3,211,209,69,15,17,103,5,144,86,89,48,68,43,16,920,185,81,272,99,33,31,115,126,898,581,20,13,327,67,277,65,2,100,13,9,100,364,268,15,4,68,24,233,78,25,51,37,301,103,17,22,272,49,3,426,39,84,33,487,20,4,53,123,19,416,688,284,349,44,63,37,77,67,372,68,307,60,849,227,30,327,127,280,22,112,548,40,46,360,121,45,20,152,78,29,201,231,95,234,134,42,392,195,173,80,162,172,60,2,16,30,96,545,555,5,101,66,725,144,8,192,228,129,12,87,24,59,360,170,338,86,83,24,225,59,52,129,67,129,64,138,58,28,6,121,5,407,347,61,264,473,55,236,147,62,158,8,109,99,21,168,144,36,85,102,77,56,24,355,34,128,123,301,54,60,113,128,348,343,164,109,83,62,28,98,134,192,55,52,52,20,31,162,279,23,33,119,205,52,223,457,53,224,107,93,116,390,214,398,14,90,161,7,6,494,198,102,184,164,306,46,60,212,37,68,47,82,31,27,317,48,243,196,8,146,151,33,146,124,4,21,313,59,761,303,375,36,480,196,82,83,11,5,125,118,482,248,38,121,40,140,41,54,54,218,178,270,17,84,80,139,300,29,52,188,51,157,80,21,348,375,444,87,290,164,186,86,114,8,49,276,47,125,12,12,41,22,742,119,512,180,753,130,4,73,12,23,224,569,137,132,115,432,5,122,184,5,12,3,137,111,1,109,248,50,12,412,124,5,20,281,83,273,503,13,11,13,554,78,159,127,21,168,53,19,531,192,20,32,196,109,329,39,4,7,110,14,176,230,32,63,156,39,205,104,4,231,616,117,167,120,130,8,411,60,25,187,24,96,211,45,145,210,49,79,129,231,133,81,212,148,115,132,508,1,95,105,126,89,5,38,90,16,358,32,22,102,1,187,65,321,64,55,349,599,555,145,416,55,197,28,149,650,118,18,285,244,296,100,216,216,20,177,1063,407,21,33,51,17,14,830,12,430,66,251,460,163,78,544,116,79,9,151,401,500,180,192,50,36,297,409,36,118,40,154,106,176,222,223,36,65,376,354,328,74,94,53,73,186,41,73,80,100,315,13,120,307,28,67,172,54,38,169,73,124,354,73,503,217,229,244,235,43,100,545,192,92,369,112,27,108,116,19,621,17,35,388,760,355,108,53,19,145,60,53,46,454,371,91,4,17,72,163,289,124,37,54,20,225,188,197,114,88,261,289,38,265,293,4,20,159,241,154,386,111,156,41,243,300,77,142,289,104,79,32,237,180,93,103,21,99,169,244,7,620,51,86,330,12,25,207,20,101,188,36,41,80,18,518,108,222,184,405,12,309,178,245,84,140,232,379,66,38,45,440,67,64,110,46,330,406,126,210,514,62,289,279,2,108,248,114,620,216,76,17,288,23,14,20,16,42,13,432,5,234,120,61,465,343,51,189,251,194,90,472,50,282,32,72,197,81,151,128,11,160,56,48,54,55,19,17,149,76,44,142,10,174,214,23,48,116,11,64,61,169,115,185,6,134,1000,31,51,10,6,453,195,58,42,265,372,297,226,118,34,273,291,16,70,254,72,98,2,469,815,193,57,250,354,140,482,5,104,353,26,232,385,75,69,7,210,311,3,42,6,70,262,93,247,457,535,13,116,33,300,180,36,7,323,229,72,16,320,77,254,137,65,11,1,78,106,38,120,185,147,161,29,50,54,339,31,421,307,4,526,163}; inline int read(){int x=0;char c=getchar();while(!isdigit(c))c=getchar();while(isdigit(c))x=x*10ll+c-48,c=getchar();return x;} inline ll rd(){ll x=0;char c=getchar();while(!isdigit(c))c=getchar();while(isdigit(c))x=x*10ll+c-48,c=getchar();return x;} inline ll pw(ll a,ll b,ll m){ll r=1;for(;b;b>>=1,a=(__int128)a*a%m)if(b&1)r=(__int128)r*a%m;return r;} inline void initpr(){for(int i=2;i<N;i++){if(!vis[i])pr[++cc]=i;for(int j=1;j<=cc&&1ll*i*pr[j]<N;j++){vis[i*pr[j]]=1;if(i%pr[j]==0)break;}}} namespace P1 { inline ll rd(ll m){ll phi=m-1,x=0;char c=getchar();while(!isdigit(c))c=getchar();while(isdigit(c)){x=(__int128)x*10+c-48,c=getchar();x%=phi;}return x;} inline void sol(ll m){ll a=rd(m);printf("%lld ",pw(19ll,a,m));} } namespace P6{inline void sol(){for(int i=0,p=1;i<100000;i++){printf("%d ",p);p=19*p%mod;}}} namespace P7{inline void sol(){for(int i=0,p=1;i<100944;i++){tb[i]=p;p=19*p%mod;}for(int i=0;i<30000;i++){ll x=rd();if(x>=55245)x-=55245,x%=45699,x+=55245;printf("%d ",tb[x]);}}} namespace P8 { const int pp[6]={2,3,5,7,13,23}; inline bool chk(ll x,ll p) { ll r=p-1;while(!(r&1))r>>=1;ll t=pw(x,r,p); for(ll y;r<p-1;r<<=1,t=y)if((y=(__int128)t*t%p)==1&&t!=1&&t!=p-1)return 0;return t==1; } inline bool mr(ll x) { for(int i=0;i<6;i++)if(x==pp[i])return 1;else if(x%pp[i]==0)return 0; for(int i=0;i<6;i++)if(!chk(pp[i],x))return 0;return 1; } inline void sol(){ll l=rd(),r=rd();for(ll i=l;i<=r;i++)if(mr(i))putchar('p');else putchar('.');putchar(' ');} } namespace P11 { inline void sol() { ll l=rd(),r=rd();for(int i=0;i<=r-l;i++)ans[i]=0,sz[i]=0,ti[i]=l+i; for(int i=1;i<=cc;i++) { ll t=l/pr[i]*pr[i]; for(;t<=r;t+=pr[i])if(t>=l)sz[(int)(t-l)]++,ti[(int)(t-l)]/=pr[i]; ll tt=1ll*pr[i]*pr[i];t=l/tt*tt; for(;t<=r;t+=tt)if(t>=l)ans[(int)(t-l)]=1; } if(l>1e12){for(int i=0;i<7171;i++)szz[t1[i]]=-1;} if(l>1e12){for(int i=0;i<6230;i++)szz[t2[i]]=1;} for(int i=0;i<=r-l;i++) { if(szz[i]){if(szz[i]==-1)putchar('+');else putchar('-');continue;} if(ti[i]!=1)sz[i]++; if(ans[i])putchar('0');else if(sz[i]&1)putchar('-');else putchar('+'); } putchar(' '); } } namespace P14 { const int pp[8]={2,3,5,7,11,13,19,23}; inline void sol() { int l=rd(),r=rd(),m=rd(),phi=m-1; if(m==998244353){for(int i=l;i<=r;i++)if(pw(i,phi/2,m)==1||pw(i,phi/7,m)==1||pw(i,phi/17,m)==1)putchar('.');else putchar('g');putchar(' ');} if(m==13123111) { for(register int i=0,j=1;i<m;i++)tg[j]=i,j=j*6%m; for(int i=0;i<8;i++)for(int j=0;j<=phi;j+=pp[i])vv[j]=1; for(register int i=1;i<m;i++)putchar(vv[tg[i]]?'.':'g'); } } } namespace P16{inline void sol(){int m=1515343657,ph=1515343656;for(int i=233333333;i<=234133333;i++)if(pw(i,ph/2,m)==1||pw(i,ph/3,m)==1||pw(i,ph/4003,m)==1||pw(i,ph/15773,m)==1)putchar('.');else putchar('g');putchar(' ');}} int main() { // freopen("software.in","r",stdin); // freopen("software.out","w",stdout); for(int i=1;i<7171;i++)t1[i]+=t1[i-1];for(int i=1;i<6230;i++)t2[i]+=t2[i-1]; char s[105];scanf("%s",s+1); if(s[1]=='1'&&s[2]=='_'){int T=read();while(T--)P1::sol(998244353);return 0;} if(s[1]=='1'&&s[2]=='?'&&s[3]=='+'){int T=read();while(T--)P1::sol(5211600617818708273ll);return 0;} if(s[1]=='1'&&s[2]=='?'){int T=read();while(T--)P1::sol(1145141);return 0;} if(s[1]=='1'&&s[2]=='w'){int T=read();if(T==100000)P6::sol();else P7::sol();return 0;} if(s[1]=='2'&&s[2]=='p'){int T=read();while(T--)P8::sol();return 0;} if(s[1]=='2'&&s[2]=='u'){initpr();int T=read();while(T--)P11::sol();return 0;} if(s[1]=='2'&&s[2]=='g'&&s[3]=='?'){puts(".g");puts(".g.gg...g");P16::sol();return 0;} if(s[1]=='2'&&s[2]=='g'){int T=read();while(T--)P14::sol();return 0;} return 0; }