n=9347147009766355127063373774379576550690862470473708730411978395107715169508952179550419799951258353;
k=89;