记录编号	76334	评测结果	AAAAAAAAAA
题目名称	[Poetize3] 大牛与神犇	最终得分	100
用户昵称	Ezoi_XY	是否通过	通过
代码语言	Pascal	运行时间	3.750 s
提交时间	2013-10-30 14:49:34	内存使用	70.25 MiB

Program cog1041;
    Type
        Bn=Array[0..3126]Of Longint;
    Var
        P:Array[1..5852]Of Longint;
        Md:Array[1..57773]Of Longint;
        S:Array[1..5852]Of Bn;
        C:Array[1..26000]Of Char;
        T,I,J,K:Longint;
        N:Bn;
        Temp:Int64;
    Function Greater(Var A,B:Bn):Boolean; Inline;
        Var
            I:Longint;
        Begin
            If A[0]>B[0] Then Exit(True);
            If A[0]<B[0] Then Exit(False);
            For I:=A[0] Downto 1 Do
                If A[I]>B[I] Then Exit(True)
                Else If A[I]<B[I] Then Exit(False);
            Exit(False);
        End;
    Procedure Mul(Var A:Bn; B:Longint); Inline;
        Var
            I:Longint;
        Begin
            Temp:=0;
            For I:=1 To A[0] Do
                Begin
                    Inc(Temp,Int64(A[I])*B);
                    A[I]:=Temp Mod 100000000;
                    Temp:=Temp Div 100000000;
                End;
            While Temp<>0 Do
                Begin
                    Inc(A[0]);
                    A[A[0]]:=Temp Mod 100000000;
                    Temp:=Temp Div 100000000;
                End;
        End;
    Begin
        Assign(Input,'heavencow.in');
        Assign(Output,'heavencow.out');
        Reset(Input);
        Rewrite(Output);
        T:=0;
        For I:=2 To 57773 Do
            Begin
                If Md[I]=0 Then
                    Begin
                        Md[I]:=I;
                        Inc(T);
                        P[T]:=I;
                    End;
                J:=1;
                While (J<=T) And (P[J]<=Md[I]) And (P[J]*I<=57773) Do
                    Begin
                        Md[P[J]*I]:=P[J];
                        Inc(J);
                    End;
            End;
        S[1][0]:=1;
        S[1][1]:=P[1];
        For I:=2 To 5852 Do
            Begin
                Move(S[I-1],S[I],(S[I-1][0]+1) Shl 2);
                Mul(S[I],P[I]);
            End;
        Readln(T);
        Repeat
            I:=0;
            While Not Eoln Do
                Begin
                    Inc(I);
                    Read(C[I]);
                End;
            Readln;
            N[0]:=0;
            For J:=I Downto 1 Do
                Begin
                    If (I-J+1) And 7=1 Then
                        Begin
                            Inc(N[0]);
                            N[N[0]]:=0;
                            K:=1;
                        End;
                    Inc(N[N[0]],K*(Ord(C[J])-48));
                    K:=K*10;
                End;
            I:=1;
            J:=5852;
            While I<J Do
                Begin
                    K:=(I+J+1) Shr 1;
                    If Greater(S[K],N)
                        Then J:=K-1
                        Else I:=K;
                End;
            Write(S[I][S[I][0]]);
            For J:=S[I][0]-1 Downto 1 Do
                Begin
                    If S[I][J]<10000000 Then Write('0');
                    If S[I][J]<1000000 Then Write('0');
                    If S[I][J]<100000 Then Write('0');
                    If S[I][J]<10000 Then Write('0');
                    If S[I][J]<1000 Then Write('0');
                    If S[I][J]<100 Then Write('0');
                    If S[I][J]<10 Then Write('0');
                    Write(S[I][J]);
                End;
            Writeln;
            Dec(T);
        Until T=0;
        Close(Input);
        Close(Output);
    End.