# Pi

Pi
You are encouraged to solve this task according to the task description, using any language you may know.
Create a program to continually calculate and output the next digit of π (pi). The program should continue forever (until it is aborted by the user) calculating and outputting each digit in succession. The output should be a decimal sequence beginning 3.14159265 ...

Note: this task is about calculating pi. For information on built-in pi constants see Real constants and functions.

## Contents

Library: GMP

uses same algorithm as Go solution, from http://web.comlab.ox.ac.uk/people/jeremy.gibbons/publications/spigot.pdf

`with Ada.Command_Line;with Ada.Text_IO;with GNU_Multiple_Precision.Big_Integers;with GNU_Multiple_Precision.Big_Rationals;use GNU_Multiple_Precision; procedure Pi_Digits is   type Int is mod 2 ** 64;   package Int_To_Big is new Big_Integers.Modular_Conversions (Int);    -- constants   Zero : constant Big_Integer := Int_To_Big.To_Big_Integer (0);   One : constant Big_Integer := Int_To_Big.To_Big_Integer (1);   Two : constant Big_Integer := Int_To_Big.To_Big_Integer (2);   Three : constant Big_Integer := Int_To_Big.To_Big_Integer (3);   Four : constant Big_Integer := Int_To_Big.To_Big_Integer (4);   Ten : constant Big_Integer := Int_To_Big.To_Big_Integer (10);    -- type LFT = (Integer, Integer, Integer, Integer   type LFT is record      Q, R, S, T : Big_Integer;   end record;    -- extr :: LFT -> Integer -> Rational   function Extr (T : LFT; X : Big_Integer) return Big_Rational is      use Big_Integers;      Result : Big_Rational;   begin      -- extr (q,r,s,t) x = ((fromInteger q) * x + (fromInteger r)) /      --                    ((fromInteger s) * x + (fromInteger t))      Big_Rationals.Set_Numerator (Item         => Result,                                   New_Value    => T.Q * X + T.R,                                   Canonicalize => False);      Big_Rationals.Set_Denominator (Item      => Result,                                     New_Value => T.S * X + T.T);      return Result;   end Extr;    -- unit :: LFT   function Unit return LFT is   begin      -- unit = (1,0,0,1)      return LFT'(Q => One, R => Zero, S => Zero, T => One);   end Unit;    -- comp :: LFT -> LFT -> LFT   function Comp (T1, T2 : LFT) return LFT is      use Big_Integers;   begin      -- comp (q,r,s,t) (u,v,w,x) = (q*u+r*w,q*v+r*x,s*u+t*w,s*v+t*x)      return LFT'(Q => T1.Q * T2.Q + T1.R * T2.S,                  R => T1.Q * T2.R + T1.R * T2.T,                  S => T1.S * T2.Q + T1.T * T2.S,                  T => T1.S * T2.R + T1.T * T2.T);   end Comp;    -- lfts = [(k, 4*k+2, 0, 2*k+1) | k<-[1..]   K : Big_Integer := Zero;   function LFTS return LFT is      use Big_Integers;   begin      K := K + One;      return LFT'(Q => K,                  R => Four * K + Two,                  S => Zero,                  T => Two * K + One);   end LFTS;    -- next z = floor (extr z 3)   function Next (T : LFT) return Big_Integer is   begin      return Big_Rationals.To_Big_Integer (Extr (T, Three));   end Next;    -- safe z n = (n == floor (extr z 4)   function Safe (T : LFT; N : Big_Integer) return Boolean is   begin      return N = Big_Rationals.To_Big_Integer (Extr (T, Four));   end Safe;    -- prod z n = comp (10, -10*n, 0, 1)   function Prod (T : LFT; N : Big_Integer) return LFT is      use Big_Integers;   begin      return Comp (LFT'(Q => Ten, R => -Ten * N, S => Zero, T => One), T);   end Prod;    procedure Print_Pi (Digit_Count : Positive) is      Z : LFT := Unit;      Y : Big_Integer;      Count : Natural := 0;   begin      loop         Y := Next (Z);         if Safe (Z, Y) then            Count := Count + 1;            Ada.Text_IO.Put (Big_Integers.Image (Y));            exit when Count >= Digit_Count;            Z := Prod (Z, Y);         else            Z := Comp (Z, LFTS);         end if;      end loop;   end Print_Pi;    N : Positive := 250;begin   if Ada.Command_Line.Argument_Count = 1 then      N := Positive'Value (Ada.Command_Line.Argument (1));   end if;   Print_Pi (N);end Pi_Digits;`

output:

` 3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4 6 2 6 4 3 3 8 3 2 7 9 5 0 2 8 8 4 1 9 7 1 6 9 3 9 9 3 7 5 1 0 5 8 2 0 9 7 4 9 4 4 5 9 2 3 0 7 8 1 6 4 0 6 2 8 6 2 0 8 9 9 8 6 2 8 0 3 4 8 2 5 3 4 2 1 1 7 0 6 7`

## ALGOL 68

Translation of: Pascal
Note: This specimen retains the original Pascal coding style of code.
Works with: ALGOL 68 version Revision 1 - no extensions to language used.
Works with: ALGOL 68G version Any - tested with release 1.18.0-9h.tiny.

This codes uses 33 decimals places as a test case. Performance is O(2) based on the number of decimal places required.

`#!/usr/local/bin/a68g --script # INT base := 10; MODE YIELDINT = PROC(INT)VOID;PROC gen pi digits = (INT decimal places, YIELDINT yield)VOID:BEGIN  INT nine = base - 1;  INT nines := 0, predigit := 0; # First predigit is a 0 #  [decimal places*10 OVER 3]#LONG# INT digits; # We need 3 times the digits to calculate #  FOR place FROM LWB digits TO UPB digits DO digits[place] := 2 OD; # Start with 2s #  FOR place TO decimal places + 1 DO    INT digit := 0;    FOR i FROM UPB digits BY -1 TO LWB digits DO # Work backwards #        INT x := #SHORTEN#(base*digits[i] + #LENG# digit*i);        digits[i] := x MOD (2*i-1);        digit := x OVER (2*i-1)    OD;    digits[LWB digits] := digit MOD base; digit OVERAB base;    nines :=       IF digit = nine THEN         nines + 1      ELSE        IF digit = base THEN          yield(predigit+1); predigit := 0 ;          FOR repeats TO nines DO yield(0) OD # zeros #         ELSE          IF place NE 1 THEN yield(predigit) FI; predigit := digit;          FOR repeats TO nines DO yield(nine) OD        FI;        0      FI  OD;  yield(predigit)END; main:(  INT feynman point = 762; # feynman point + 4 is a good test case ## the 33rd decimal place is a shorter tricky test case #  INT test decimal places = UPB "3.1415926.......................502"-2;   INT width = ENTIER log(base*(1+small real*10));  # iterate throught the digits as they are being found ## FOR INT digit IN # gen pi digits(test decimal places#) DO ( #,  ## (INT digit)VOID: (    printf((\$n(width)d\$,digit))  )# OD #);  print(new line))`

Output:

```3141592653589793238462643383279502
```

## BASIC256

Translation of: Pascal
`cls n   =1000len = 10*n \ 4needdecimal = truedim a(len)nines = 0predigit = 0	# {First predigit is a 0} for j = 1 to len   a[j-1] = 2	# {Start with 2s}next j for j = 1 to n   q = 0   for i = len to 1 step -1      #  {Work backwards}      x   = 10*a[i-1] + q*i      a[i-1] = x % (2*i - 1)      q    = x \ (2*i - 1)   next i   a[0] = q % 10   q = q \ 10   if q = 9 then      nines = nines + 1   else      if q = 10 then         d = predigit+1: gosub outputd         if nines > 0 then            for k = 1 to nines               d =  0: gosub outputd            next k         end if         predigit = 0         nines = 0      else         d = predigit: gosub outputd         predigit = q         if nines <> 0 then            for k = 1 to nines               d =  9: gosub outputd            next k            nines = 0         end if      end if   end ifnext jprint predigitend outputd:if needdecimal then   if d = 0 then return   print d + ".";   needdecimal = falseelse   print d;end ifreturn`

Output: 3.14159265358979323846264338327950288419716939937510582097494459230781640628620899862803482534211706798214808651328230664709384460955058223172535940812848111745028410270193852110555964462294895...

## BBC BASIC

### BASIC version

`      WIDTH 80      M% = (HIMEM-END-1000) / 4      DIM B%(M%)      FOR I% = 0 TO M% : B%(I%) = 20 : NEXT      E% = 0      L% = 2      FOR C% = M% TO 14 STEP -7        D% = 0        A% = C%*2-1        FOR P% = C% TO 1 STEP -1          D% = D%*P% + B%(P%)*&64          B%(P%) = D% MOD A%          D% DIV= A%          A% -= 2        NEXT        CASE TRUE OF          WHEN D% = 99: E% = E% * 100 + D% : L% += 2          WHEN C% = M%: PRINT ;(D% DIV 100) / 10; : E% = D% MOD 100          OTHERWISE:            PRINT RIGHT\$(STRING\$(L%,"0") + STR\$(E% + D% DIV 100),L%);            E% = D% MOD 100 : L% = 2        ENDCASE      NEXT`

### Assembler version

The first 250,000 digits output have been verified.

`      DIM P% 32      [OPT 2 :.pidig mov ebp,eax :.pi1 imul edx,ecx : mov eax,[ebx+ecx*4]      imul eax,100 : add eax,edx : cdq : div ebp : mov [ebx+ecx*4],edx      mov edx,eax : sub ebp,2 : loop pi1 : mov eax,edx : ret :]       WIDTH 80      M% = (HIMEM-END-1000) / 4      DIM B%(M%) : B% = ^B%(0)      FOR I% = 0 TO M% : B%(I%) = 20 : NEXT      E% = 0      L% = 2      FOR C% = M% TO 14 STEP -7        D% = 0        A% = C%*2-1        D% = USR(pidig)        CASE TRUE OF          WHEN D% = 99: E% = E% * 100 + D% : L% += 2          WHEN C% = M%: PRINT ;(D% DIV 100) / 10; : E% = D% MOD 100          OTHERWISE:            PRINT RIGHT\$(STRING\$(L%,"0") + STR\$(E% + D% DIV 100),L%);            E% = D% MOD 100 : L% = 2        ENDCASE      NEXT`

Output:

```3.141592653589793238462643383279502884197169399375105820974944592307816406286208
99862803482534211706798214808651328230664709384460955058223172535940812848111745
02841027019385211055596446229489549303819644288109756659334461284756482337867831
65271201909145648566923460348610454326648213393607260249141273724587006606315588
17488152092096282925409171536436789259036001133053054882046652138414695194151160
94330572703657595919530921861173819326117931051185480744623799627495673518857527
24891227938183011949129833673362440656643086021394946395224737190702179860943702
77053921717629317675238467481846766940513200056812714526356082778577134275778960
91736371787214684409012249534301465495853710507922796892589235420199561121290219
60864034418159813629774771309960518707211349999998372978049951059731732816096318
....
```

## bc

The digits of Pi are printed 20 per line, by successively recomputing pi with higher precision. The computation is not accurate to the entire scale (for example, `scale = 4; 4*a(1)` prints 3.1412 instead of the expected 3.1415), so the program includes two excess digits in the scale. Fixed number of guarding digits will eventually fail because Pi can contain arbitrarily long sequence of consecutive 9s (or consecutive 0s), though for this task it might not matter in practice. The program proceeds more and more slowly but exploits bc's unlimited precision arithmetic.

The program uses three features of GNU bc: long variable names, # comments (for the #! line), and the `print` command (for zero padding).

Library: bc -l
Works with: GNU bc
Works with: OpenBSD bc
`#!/usr/bin/bc -l scaleinc= 20 define zeropad ( n ) {    auto m    for ( m= scaleinc - 1; m > 0; --m ) {        if ( n < 10^m ) {            print "0"        }    }    return ( n )} wantscale= scaleinc - 2scale= wantscale + 2oldpi= 4*a(1)scale= wantscaleoldpi= oldpi / 1oldpiwhile( 1 ) {    wantscale= wantscale + scaleinc    scale= wantscale + 2    pi= 4*a(1)    scale= 0    digits= ((pi - oldpi) * 10^wantscale) / 1    zeropad( digits )    scale= wantscale    oldpi= pi / 1}`

Output:

```3.141592653589793238
46264338327950288419
71693993751058209749
44592307816406286208
99862803482534211706
79821480865132823066
47093844609550582231
72535940812848111745
02841027019385211055
59644622948954930381
96442881097566593344
61284756482337867831
65271201909145648566
92346034861045432664
82133936072602491412
73724587006606315588
17488152092096282925
40917153643678925903
60011330530548820466
52138414695194151160
94330572703657595919
....
```

## Bracmat

Translation of: Icon_and_Unicon
`  ( pi  =   f,q r t k n l,first    .   !arg:((=?f),?q,?r,?t,?k,?n,?l)      & yes:?first      &   whl        ' (   4*!q+!r+-1*!t+-1*!n*!t:<0            & f\$!n            & (   !first:yes                & f\$"."                & no:?first              |               )            & "compute and update variables for next cycle"            & 10*(!r+-1*!n*!t):?nr            & div\$(10*(3*!q+!r).!t)+-10*!n:?n            & !q*10:?q            & !nr:?r          |   "compute and update variables for next cycle"            & (2*!q+!r)*!l:?nr            & div\$(!q*(7*!k+2)+!r*!l.!t*!l):?nn            & !q*!k:?q            & !t*!l:?t            & !l+2:?l            & !k+1:?k            & !nn:?n            & !nr:?r          )  )& pi\$((=.put\$!arg),1,0,1,1,3,3)`

Output:

```3.1415926535897932384626433832795028841971693993751058209749445923078164062
862089986280348253421170679821480865132823066470938446095505822317253594081
284811174502841027019385211055596446229489549303819644288109756659334461284
756482337867831652712019091456485669234603486104543266482133936072602491412
73724587006606315588174881520^C```

## C

Using Machin's formula. The "continuous printing" part is silly: the algorithm really calls for a preset number of digits, so the program repeatedly calculates Pi digits with increasing length and chop off leading digits already displayed. But it's still faster than the unbounded Spigot method by an order of magnitude, at least for the first 100k digits.

`#include <stdio.h>#include <stdlib.h>#include <gmp.h> mpz_t tmp1, tmp2, t5, t239, pows;void actan(mpz_t res, unsigned long base, mpz_t pows){	int i, neg = 1;	mpz_tdiv_q_ui(res, pows, base);	mpz_set(tmp1, res);	for (i = 3; ; i += 2) {		mpz_tdiv_q_ui(tmp1, tmp1, base * base);		mpz_tdiv_q_ui(tmp2, tmp1, i);		if (mpz_cmp_ui(tmp2, 0) == 0) break;		if (neg) mpz_sub(res, res, tmp2);		else	  mpz_add(res, res, tmp2);		neg = !neg;	}} char * get_digits(int n, size_t* len){	mpz_ui_pow_ui(pows, 10, n + 20); 	actan(t5, 5, pows);	mpz_mul_ui(t5, t5, 16); 	actan(t239, 239, pows);	mpz_mul_ui(t239, t239, 4); 	mpz_sub(t5, t5, t239);	mpz_ui_pow_ui(pows, 10, 20);	mpz_tdiv_q(t5, t5, pows); 	*len = mpz_sizeinbase(t5, 10);	return mpz_get_str(0, 0, t5);} int main(int c, char **v){	unsigned long accu = 16384, done = 0;	size_t got;	char *s; 	mpz_init(tmp1);	mpz_init(tmp2);	mpz_init(t5);	mpz_init(t239);	mpz_init(pows); 	while (1) {		s = get_digits(accu, &got); 		/* write out digits up to the last one not preceding a 0 or 9*/		got -= 2; /* -2: length estimate may be longer than actual */		while (s[got] == '0' || s[got] == '9') got--; 		printf("%.*s", (int)(got - done), s + done);		free(s); 		done = got; 		/* double the desired digits; slows down at least cubically */		accu *= 2;	} 	return 0;}`

## C++

Library: gmp
`#include "gmp.h" void agm (const mpf_t in1, const mpf_t in2, mpf_t out1, mpf_t out2) {	mpf_add (out1, in1, in2);	mpf_div_ui (out1, out1, 2);	mpf_mul (out2, in1, in2);	mpf_sqrt (out2, out2);} int main (void) {	mpf_set_default_prec (300000);	mpf_t x0, y0, resA, resB, Z, var; 	mpf_init_set_ui (x0, 1);	mpf_init_set_d (y0, 0.5);	mpf_sqrt (y0, y0);	mpf_init (resA);	mpf_init (resB);	mpf_init_set_d (Z, 0.25);	mpf_init (var); 	int n = 1;	for(int i=0; i<8; i++){		agm(x0, y0, resA, resB);		mpf_sub(var, resA, x0);		mpf_mul(var, var, var);		mpf_mul_ui(var, var, n);		mpf_sub(Z, Z, var);		n += n;		agm(resA, resB, x0, y0);		mpf_sub(var, x0, resA);		mpf_mul(var, var, var);		mpf_mul_ui(var, var, n);		mpf_sub(Z, Z, var);		n += n;	}	mpf_mul(x0, x0, x0);	mpf_div(x0, x0, Z);	gmp_printf ("%.100000Ff\n", x0);	return 0;}`

i<7 produces:

```3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679821480865132823066470938446095505822317253594081284811174502841027019385211055596446229489549303819644288109756659334461284756482337867831652712019091456485669234603486104543266482133936072602491412737245870066063155881748815209209628292540917153643678925903600113305305488204665213841469519415116094330572703657595919530921861173819326117931051185480744623799627495673518857527248912279381830119491298336733624406566430860213949463952247371907021798609437027705392171762931767523846748184676694051320005681271452635608277857713427577896091736371787214684409012249534301465495853710507922796892589235420199561121290219608640344181598136297747713099605187072113499999983729780499510597317328160963185950244594553469083026425223082533446850352619311881710100031378387528865875332083814206171776691473035982534904287554687311595628638823537875937519577818577805321712268066130019278766111959092164201989380952572010654858632788659361533818279682303019520353018529689957736225994138912497217752834791315155748572424541506959508295331168617278558890750983817546374649393192550604009277016711390098488240128583616035637076601047101819429555961989467678374494482553797747268471040475346462080466842590694912933136770289891521047521620569660240580381501935112533824300355876402474964732639141992726042699227967823547816360093417216412199245863150302861829745557067498385054945885869269956909272107975093029553211653449872027559602364806654991198818347977535663698074265425278625518184175746728909777727938000816470600161452491921732172147723501414419735685481613611573525521334757418494684385233239073941433345477624168625189835694855620992192221842725502542568876717904946016534668049886272327917860857843838279679766814541009538837863609506800642251252051173929848960841284886269456042419652850222106611863067442786220391949450471237137869609563643719172874677646575739624138908658326459958133904780275900994657640789512694683983525957098258226205224894077267194782684826014769909026401363944374553050682034962524517493996514314298091906592509372216964615157098583874105978859597729754989301617539284681382686838689427741559918559252459539594310499725246808459872736446958486538367362226260991246080512438843904512441365497627807977156914359977001296160894416948685558484063534220722258284886481584560285060168427394522674676788952521385225499546667278239864565961163548862305774564980355936345681743241125150760694794510965960940252288797108931456691368672287489405601015033086179286809208747609178249385890097149096759852613655497818931297848216829989487226588048575640142704775551323796414515237462343645428584447952658678210511413547357395231134271661021359695362314429524849371871101457654035902799344037420073105785390621983874478084784896833214457138687519435064302184531910484810053706146806749192781911979399520614196634287544406437451237181921799983910159195618146751426912397489409071864942319615679452080951465502252316038819301420937621378559566389377870830390697920773467221825625996615014215030680384477345492026054146659252014974428507325186660021324340881907104863317346496514539057962685610055081066587969981635747363840525714591028970641401109712062804390397595156771577004203378699360072305587631763594218731251471205329281918261861258673215791984148488291644706095752706957220917567116722910981690915280173506712748583222871835209353965725121083579151369882091444210067510334671103141267111369908658516398315019701651511685171437657618351556508849099898599823873455283316355076479185358932261854896321329330898570642046752590709154814165498594616371802709819943099244889575712828905923233260972997120844335732654893823911932597463667305836041428138830320382490375898524374417029132765618093773444030707469211201913020330380197621101100449293215160842444859637669838952286847831235526582131449576857262433441893039686426243410773226978028073189154411010446823252716201052652272111660396665573092547110557853763466820653109896526918620564769312570586356620185581007293606598764861179104533488503461136576867532494416680396265797877185560845529654126654085306143444318586769751456614068007002378776591344017127494704205622305389945613140711270004078547332699390814546646458807972708266830634328587856983052358089330657574067954571637752542021149557615814002501262285941302164715509792592309907965473761255176567513575178296664547791745011299614890304639947132962107340437518957359614589019389713111790429782856475032031986915140287080859904801094121472213179476477726224142548545403321571853061422881375850430633217518297986622371721591607716692547487389866549494501146540628433663937900397692656721463853067360965712091807638327166416274888800786925602902284721040317211860820419000422966171196377921337575114959501566049631862947265473642523081770367515906735023507283540567040386743513622224771589150495309844489333096340878076932599397805419341447377441842631298608099888687413260472156951623965864573021631598193195167353812974167729478672422924654366800980676928238280689964004824354037014163149658979409243237896907069779422362508221688957383798623001593776471651228935786015881617557829735233446042815126272037343146531977774160319906655418763979293344195215413418994854447345673831624993419131814809277771038638773431772075456545322077709212019051660962804909263601975988281613323166636528619326686336062735676303544776280350450777235547105859548702790814356240145171806246436267945612753181340783303362542327839449753824372058353114771199260638133467768796959703098339130771098704085913374641442822772634659470474587847787201927715280731767907707157213444730605700733492436931138350493163128404251219256517980694113528013147013047816437885185290928545201165839341965621349143415956258658655705526904965209858033850722426482939728584783163057777560688876446248246857926039535277348030480290058760758251047470916439613626760449256274204208320856611906254543372131535958450687724602901618766795240616342522577195429162991930645537799140373404328752628889639958794757291746426357455254079091451357111369410911939325191076020825202618798531887705842972591677813149699009019211697173727847684726860849003377024242916513005005168323364350389517029893922334517220138128069650117844087451960121228599371623130171144484640903890644954440061986907548516026327505298349187407866808818338510228334508504860825039302133219715518430635455007668282949304137765527939751754613953984683393638304746119966538581538420568533862186725233402830871123282789212507712629463229563989898935821167456270102183564622013496715188190973038119800497340723961036854066431939509790190699639552453005450580685501956730229219139339185680344903982059551002263535361920419947455385938102343955449597783779023742161727111723643435439478221818528624085140066604433258885698670543154706965747458550332323342107301545940516553790686627333799585115625784322988273723198987571415957811196358330059408730681216028764962867446047746491599505497374256269010490377819868359381465741268049256487985561453723478673303904688383436346553794986419270563872931748723320837601123029911367938627089438799362016295154133714248928307220126901475466847653576164773794675200490757155527819653621323926406160136358155907422020203187277605277219005561484255518792530343513984425322341576233610642506390497500865627109535919465897514131034822769306247435363256916078154781811528436679570611086153315044521274739245449454236828860613408414863776700961207151249140430272538607648236341433462351897576645216413767969031495019108575984423919862916421939949072362346468441173940326591840443780513338945257423995082965912285085558215725031071257012668302402929525220118726767562204154205161841634847565169998116141010029960783869092916030288400269104140792886215078424516709087000699282120660418371806535567252532567532861291042487761825829765157959847035622262934860034158722980534989650226291748788202734209222245339856264766914905562842503912757710284027998066365825488926488025456610172967026640765590429099456815065265305371829412703369313785178609040708667114965583434347693385781711386455873678123014587687126603489139095620099393610310291616152881384379099042317473363948045759314931405297634757481193567091101377517210080315590248530906692037671922033229094334676851422144773793937517034436619910403375111735471918550464490263655128162288244625759163330391072253837421821408835086573917715096828874782656995995744906617583441375223970968340800535598491754173818839994469748676265516582765848358845314277568790029095170283529716344562129640435231176006651012412006597558512761785838292041974844236080071930457618932349229279650198751872127267507981255470958904556357921221033346697499235630254947802490114195212382815309114079073860251522742995818072471625916685451333123948049470791191532673430282441860414263639548000448002670496248201792896476697583183271314251702969234889627668440323260927524960357996469256504936818360900323809293459588970695365349406034021665443755890045632882250545255640564482465151875471196218443965825337543885690941130315095261793780029741207665147939425902989695946995565761218656196733786236256125216320862869222103274889218654364802296780705765615144632046927906821207388377814233562823608963208068222468012248261177185896381409183903673672220888321513755600372798394004152970028783076670944474560134556417254370906979396122571429894671543578468788614445812314593571984922528471605049221242470141214780573455105008019086996033027634787081081754501193071412233908663938339529425786905076431006383519834389341596131854347546495569781038293097164651438407007073604112373599843452251610507027056235266012764848308407611830130527932054274628654036036745328651057065874882256981579367897669742205750596834408697350201410206723585020072452256326513410559240190274216248439140359989535394590944070469120914093870012645600162374288021092764579310657922955249887275846101264836999892256959688159205600101655256375678566722796619885782794848855834397518744545512965634434803966420557982936804352202770984294232533022576341807039476994159791594530069752148293366555661567873640053666564165473217043903521329543529169414599041608753201868379370234888689479151071637852902345292440773659495630510074210871426134974595615138498713757047101787957310422969066670214498637464595280824369445789772330048764765241339075920434019634039114732023380715095222010682563427471646024335440051521266932493419673977041595683753555166730273900749729736354964533288869844061196496162773449518273695588220757355176651589855190986665393549481068873206859907540792342402300925900701731960362254756478940647548346647760411463233905651343306844953979070903023460461470961696886885014083470405460742958699138296682468185710318879065287036650832431974404771855678934823089431068287027228097362480939962706074726455399253994428081137369433887294063079261595995462624629707062594845569034711972996409089418059534393251236235508134949004364278527138315912568989295196427287573946914272534366941532361004537304881985517065941217352462589548730167600298865925786628561249665523533829428785425340483083307016537228563559152534784459818313411290019992059813522051173365856407826484942764411376393866924803118364453698589175442647399882284621844900877769776312795722672655562596282542765318300134070922334365779160128093179401718598599933849235495640057099558561134980252499066984233017350358044081168552653117099570899427328709258487894436460050410892266917835258707859512983441729535195378855345737426085902908176515578039059464087350612322611200937310804854852635722825768203416050484662775045003126200800799804925485346941469775164932709504934639382432227188515974054702148289711177792376122578873477188196825462981268685817050740272550263329044976277894423621674119186269439650671515779586756482399391760426017633870454990176143641204692182370764887834196896861181558158736062938603810171215855272668300823834046564758804051380801633638874216371406435495561868964112282140753302655100424104896783528588290243670904887118190909494533144218287661810310073547705498159680772009474696134360928614849417850171807793068108546900094458995279424398139213505586422196483491512639012803832001097738680662877923971801461343244572640097374257007359210031541508936793008169980536520276007277496745840028362405346037263416554259027601834840306811381855105979705664007509426087885735796037324514146786703688098806097164258497595138069309449401515422221943291302173912538355915031003330325111749156969174502714943315155885403922164097229101129035521815762823283182342548326111912800928252561902052630163911477247331485739107775874425387611746578671169414776421441111263583553871361011023267987756410246824032264834641766369806637857681349204530224081972785647198396308781543221166912246415911776732253264335686146186545222681268872684459684424161078540167681420808850280054143613146230821025941737562389942075713627516745731891894562835257044133543758575342698699472547031656613991999682628247270641336222178923903176085428943733935618891651250424404008952719837873864805847268954624388234375178852014395600571048119498842390606136957342315590796703461491434478863604103182350736502778590897578272731305048893989009923913503373250855982655867089242612429473670193907727130706869170926462548423240748550366080136046689511840093668609546325002145852930950000907151058236267293264537382104938724996699339424685516483261134146110680267446637334375340764294026682973865220935701626384648528514903629320199199688285171839536691345222444708045923966028171565515656661113598231122506289058549145097157553900243931535190902107119457300243880176615035270862602537881797519478061013715004489917210022201335013106016391541589578037117792775225978742891917915522417189585361680594741234193398420218745649256443462392531953135103311476394911995072858430658361935369329699289837914941939406085724863968836903265564364216644257607914710869984315733749648835292769328220762947282381537409961545598798259891093717126218283025848112389011968221429457667580718653806506487026133892822994972574530332838963818439447707794022843598834100358385423897354243956475556840952248445541392394100016207693636846776413017819659379971557468541946334893748439129742391433659360410035234377706588867781139498616478747140793263858738624732889645643598774667638479466504074111825658378878454858148962961273998413442726086061872455452360643153710112746809778704464094758280348769758948328241239292960582948619196670918958089833201210318430340128495116203534280144127617285830243559830032042024512072872535581195840149180969253395075778400067465526031446167050827682772223534191102634163157147406123850425845988419907611287258059113935689601431668283176323567325417073420817332230462987992804908514094790368878687894930546955703072619009502076433493359106024545086453628935456862958531315337183868265617862273637169757741830239860065914816164049449650117321313895747062088474802365371031150898427992754426853277974311395143574172219759799359685252285745263796289612691572357986620573408375766873884266405990993505000813375432454635967504844235284874701443545419576258473564216198134073468541117668831186544893776979566517279662326714810338643913751865946730024434500544995399742372328712494834706044063471606325830649829795510109541836235030309453097335834462839476304775645015008507578949548931393944899216125525597701436858943585877526379625597081677643800125436502371412783467926101995585224717220177723700417808419423948725406801556035998390548985723546745642390585850216719031395262944554391316631345308939062046784387785054239390524731362012947691874975191011472315289326772533918146607300089027768963114810902209724520759167297007850580717186381054967973100167870850694207092232908070383263453452038027860990556900134137182368370991949516489600755049341267876436746384902063964019766685592335654639138363185745698147196210841080961884605456039038455343729141446513474940784884423772175154334260306698831768331001133108690421939031080143784334151370924353013677631084913516156422698475074303297167469640666531527035325467112667522460551199581831963763707617991919203579582007595605302346267757943936307463056901080114942714100939136913810725813781357894005599500183542511841721360557275221035268037357265279224173736057511278872181908449006178013889710770822931002797665935838758909395688148560263224393726562472776037890814458837855019702843779362407825052704875816470324581290878395232453237896029841669225489649715606981192186584926770403956481278102179913217416305810554598801300484562997651121241536374515005635070127815926714241342103301566165356024733807843028655257222753049998837015348793008062601809623815161366903341111386538510919367393835229345888322550887064507539473952043968079067086806445096986548801682874343786126453815834280753061845485903798217994599681154419742536344399602902510015888272164745006820704193761584547123183460072629339550548239557137256840232268213012476794522644820910235647752723082081063518899152692889108455571126603965034397896278250016110153235160519655904211844949907789992007329476905868577878720982901352956613978884860509786085957017731298155314951681467176959760994210036183559138777817698458758104466283998806006162298486169353373865787735983361613384133853684211978938900185295691967804554482858483701170967212535338758621582310133103877668272115726949518179589754693992642197915523385766231676275475703546994148929041301863861194391962838870543677743224276809132365449485366768000001065262485473055861598999140170769838548318875014293890899506854530765116803337322265175662207526951791442252808165171667766727930354851542040238174608923283917032754257508676551178593950027933895920576682789677644531840404185540104351348389531201326378369283580827193783126549617459970567450718332065034556644034490453627560011250184335607361222765949278393706478426456763388188075656121689605041611390390639601620221536849410926053876887148379895599991120991646464411918568277004574243434021672276445589330127781586869525069499364610175685060167145354315814801054588605645501332037586454858403240298717093480910556211671546848477803944756979804263180991756422809873998766973237695737015808068229045992123661689025962730430679316531149401764737693873514093361833216142802149763399189835484875625298752423873077559555955465196394401821840998412489826236737714672260616336432964063357281070788758164043814850188411431885988276944901193212968271588841338694346828590066640806314077757725705630729400492940302420498416565479736705485580445865720227637840466823379852827105784319753541795011347273625774080213476826045022851579795797647467022840999561601569108903845824502679265942055503958792298185264800706837650418365620945554346135134152570065974881916341359556719649654032187271602648593049039787489589066127250794828276938953521753621850796297785146188432719223223810158744450528665238022532843891375273845892384422535472653098171578447834215822327020690287232330053862163479885094695472004795231120150432932266282727632177908840087861480221475376578105819702226309717495072127248479478169572961423658595782090830733233560348465318730293026659645013718375428897557971449924654038681799213893469244741985097334626793321072686870768062639919361965044099542167627840914669856925715074315740793805323925239477557441591845821562518192155233709607483329234921034514626437449805596103307994145347784574699992128599999399612281615219314888769388022281083001986016549416542616968586788372609587745676182507275992950893180521872924610867639958916145855058397274209809097817293239301067663868240401113040247007350857828724627134946368531815469690466968693925472519413992914652423857762550047485295476814795467007050347999588867695016124972282040303995463278830695976249361510102436555352230690612949388599015734661023712235478911292547696176005047974928060721268039226911027772261025441492215765045081206771735712027180242968106203776578837166909109418074487814049075517820385653909910477594141321543284406250301802757169650820964273484146957263978842560084531214065935809041271135920041975985136254796160632288736181367373244506079244117639975974619383584574915988097667447093006546342423460634237474666080431701260052055928493695941434081468529815053947178900451835755154125223590590687264878635752541911288877371766374860276606349603536794702692322971868327717393236192007774522126247518698334951510198642698878471719396649769070825217423365662725928440620430214113719922785269984698847702323823840055655517889087661360130477098438611687052310553149162517283732728676007248172987637569816335415074608838663640693470437206688651275688266149730788657015685016918647488541679154596507234287730699853713904300266530783987763850323818215535597323530686043010675760838908627049841888595138091030423595782495143988590113185835840667472370297149785084145853085781339156270760356390763947311455495832266945702494139831634332378975955680856836297253867913275055542524491943589128405045226953812179131914513500993846311774017971512283785460116035955402864405902496466930707769055481028850208085800878115773817191741776017330738554758006056014337743299012728677253043182519757916792969965041460706645712588834697979642931622965520168797300035646304579308840327480771811555330909887025505207680463034608658165394876951960044084820659673794731680864156456505300498816164905788311543454850526600698230931577765003780704661264706021457505793270962047825615247145918965223608396645624105195510522357239739512881816405978591427914816542632892004281609136937773722299983327082082969955737727375667615527113922588055201898876201141680054687365580633471603734291703907986396522961312801782679717289822936070288069087768660593252746378405397691848082041021944719713869256084162451123980620113184541244782050110798760717155683154078865439041210873032402010685341947230476666721749869868547076781205124736792479193150856444775379853799732234456122785843296846647513336573692387201464723679427870042503255589926884349592876124007558756946413705625140011797133166207153715436006876477318675587148783989081074295309410605969443158477539700943988394914432353668539209946879645066533985738887866147629443414010498889931600512076781035886116602029611936396821349607501116498327856353161451684576956871090029997698412632665023477167286573785790857466
```

i<8 produces:

```3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342117067982148086513282306647093844609550582231725359408128481117450284102701938521105559644622948954930381964428810975665933446128475648233786783165271201909145648566923460348610454326648213393607260249141273724587006606315588174881520920962829254091715364367892590360011330530548820466521384146951941511609433057270365759591953092186117381932611793105118548074462379962749567351885752724891227938183011949129833673362440656643086021394946395224737190702179860943702770539217176293176752384674818467669405132000568127145263560827785771342757789609173637178721468440901224953430146549585371050792279689258923542019956112129021960864034418159813629774771309960518707211349999998372978049951059731732816096318595024459455346908302642522308253344685035261931188171010003137838752886587533208381420617177669147303598253490428755468731159562863882353787593751957781857780532171226806613001927876611195909216420198938095257201065485863278865936153381827968230301952035301852968995773622599413891249721775283479131515574857242454150695950829533116861727855889075098381754637464939319255060400927701671139009848824012858361603563707660104710181942955596198946767837449448255379774726847104047534646208046684259069491293313677028989152104752162056966024058038150193511253382430035587640247496473263914199272604269922796782354781636009341721641219924586315030286182974555706749838505494588586926995690927210797509302955321165344987202755960236480665499119881834797753566369807426542527862551818417574672890977772793800081647060016145249192173217214772350141441973568548161361157352552133475741849468438523323907394143334547762416862518983569485562099219222184272550254256887671790494601653466804988627232791786085784383827967976681454100953883786360950680064225125205117392984896084128488626945604241965285022210661186306744278622039194945047123713786960956364371917287467764657573962413890865832645995813390478027590099465764078951269468398352595709825822620522489407726719478268482601476990902640136394437455305068203496252451749399651431429809190659250937221696461515709858387410597885959772975498930161753928468138268683868942774155991855925245953959431049972524680845987273644695848653836736222626099124608051243884390451244136549762780797715691435997700129616089441694868555848406353422072225828488648158456028506016842739452267467678895252138522549954666727823986456596116354886230577456498035593634568174324112515076069479451096596094025228879710893145669136867228748940560101503308617928680920874760917824938589009714909675985261365549781893129784821682998948722658804857564014270477555132379641451523746234364542858444795265867821051141354735739523113427166102135969536231442952484937187110145765403590279934403742007310578539062198387447808478489683321445713868751943506430218453191048481005370614680674919278191197939952061419663428754440643745123718192179998391015919561814675142691239748940907186494231961567945208095146550225231603881930142093762137855956638937787083039069792077346722182562599661501421503068038447734549202605414665925201497442850732518666002132434088190710486331734649651453905796268561005508106658796998163574736384052571459102897064140110971206280439039759515677157700420337869936007230558763176359421873125147120532928191826186125867321579198414848829164470609575270695722091756711672291098169091528017350671274858322287183520935396572512108357915136988209144421006751033467110314126711136990865851639831501970165151168517143765761835155650884909989859982387345528331635507647918535893226185489632132933089857064204675259070915481416549859461637180270981994309924488957571282890592323326097299712084433573265489382391193259746366730583604142813883032038249037589852437441702913276561809377344403070746921120191302033038019762110110044929321516084244485963766983895228684783123552658213144957685726243344189303968642624341077322697802807318915441101044682325271620105265227211166039666557309254711055785376346682065310989652691862056476931257058635662018558100729360659876486117910453348850346113657686753249441668039626579787718556084552965412665408530614344431858676975145661406800700237877659134401712749470420562230538994561314071127000407854733269939081454664645880797270826683063432858785698305235808933065757406795457163775254202114955761581400250126228594130216471550979259230990796547376125517656751357517829666454779174501129961489030463994713296210734043751895735961458901938971311179042978285647503203198691514028708085990480109412147221317947647772622414254854540332157185306142288137585043063321751829798662237172159160771669254748738986654949450114654062843366393790039769265672146385306736096571209180763832716641627488880078692560290228472104031721186082041900042296617119637792133757511495950156604963186294726547364252308177036751590673502350728354056704038674351362222477158915049530984448933309634087807693259939780541934144737744184263129860809988868741326047215695162396586457302163159819319516735381297416772947867242292465436680098067692823828068996400482435403701416314965897940924323789690706977942236250822168895738379862300159377647165122893578601588161755782973523344604281512627203734314653197777416031990665541876397929334419521541341899485444734567383162499341913181480927777103863877343177207545654532207770921201905166096280490926360197598828161332316663652861932668633606273567630354477628035045077723554710585954870279081435624014517180624643626794561275318134078330336254232783944975382437205835311477119926063813346776879695970309833913077109870408591337464144282277263465947047458784778720192771528073176790770715721344473060570073349243693113835049316312840425121925651798069411352801314701304781643788518529092854520116583934196562134914341595625865865570552690496520985803385072242648293972858478316305777756068887644624824685792603953527734803048029005876075825104747091643961362676044925627420420832085661190625454337213153595845068772460290161876679524061634252257719542916299193064553779914037340432875262888963995879475729174642635745525407909145135711136941091193932519107602082520261879853188770584297259167781314969900901921169717372784768472686084900337702424291651300500516832336435038951702989392233451722013812806965011784408745196012122859937162313017114448464090389064495444006198690754851602632750529834918740786680881833851022833450850486082503930213321971551843063545500766828294930413776552793975175461395398468339363830474611996653858153842056853386218672523340283087112328278921250771262946322956398989893582116745627010218356462201349671518819097303811980049734072396103685406643193950979019069963955245300545058068550195673022921913933918568034490398205955100226353536192041994745538593810234395544959778377902374216172711172364343543947822181852862408514006660443325888569867054315470696574745855033232334210730154594051655379068662733379958511562578432298827372319898757141595781119635833005940873068121602876496286744604774649159950549737425626901049037781986835938146574126804925648798556145372347867330390468838343634655379498641927056387293174872332083760112302991136793862708943879936201629515413371424892830722012690147546684765357616477379467520049075715552781965362132392640616013635815590742202020318727760527721900556148425551879253034351398442532234157623361064250639049750086562710953591946589751413103482276930624743536325691607815478181152843667957061108615331504452127473924544945423682886061340841486377670096120715124914043027253860764823634143346235189757664521641376796903149501910857598442391986291642193994907236234646844117394032659184044378051333894525742399508296591228508555821572503107125701266830240292952522011872676756220415420516184163484756516999811614101002996078386909291603028840026910414079288621507842451670908700069928212066041837180653556725253256753286129104248776182582976515795984703562226293486003415872298053498965022629174878820273420922224533985626476691490556284250391275771028402799806636582548892648802545661017296702664076559042909945681506526530537182941270336931378517860904070866711496558343434769338578171138645587367812301458768712660348913909562009939361031029161615288138437909904231747336394804575931493140529763475748119356709110137751721008031559024853090669203767192203322909433467685142214477379393751703443661991040337511173547191855046449026365512816228824462575916333039107225383742182140883508657391771509682887478265699599574490661758344137522397096834080053559849175417381883999446974867626551658276584835884531427756879002909517028352971634456212964043523117600665101241200659755851276178583829204197484423608007193045761893234922927965019875187212726750798125547095890455635792122103334669749923563025494780249011419521238281530911407907386025152274299581807247162591668545133312394804947079119153267343028244186041426363954800044800267049624820179289647669758318327131425170296923488962766844032326092752496035799646925650493681836090032380929345958897069536534940603402166544375589004563288225054525564056448246515187547119621844396582533754388569094113031509526179378002974120766514793942590298969594699556576121865619673378623625612521632086286922210327488921865436480229678070576561514463204692790682120738837781423356282360896320806822246801224826117718589638140918390367367222088832151375560037279839400415297002878307667094447456013455641725437090697939612257142989467154357846878861444581231459357198492252847160504922124247014121478057345510500801908699603302763478708108175450119307141223390866393833952942578690507643100638351983438934159613185434754649556978103829309716465143840700707360411237359984345225161050702705623526601276484830840761183013052793205427462865403603674532865105706587488225698157936789766974220575059683440869735020141020672358502007245225632651341055924019027421624843914035998953539459094407046912091409387001264560016237428802109276457931065792295524988727584610126483699989225695968815920560010165525637567856672279661988578279484885583439751874454551296563443480396642055798293680435220277098429423253302257634180703947699415979159453006975214829336655566156787364005366656416547321704390352132954352916941459904160875320186837937023488868947915107163785290234529244077365949563051007421087142613497459561513849871375704710178795731042296906667021449863746459528082436944578977233004876476524133907592043401963403911473202338071509522201068256342747164602433544005152126693249341967397704159568375355516673027390074972973635496453328886984406119649616277344951827369558822075735517665158985519098666539354948106887320685990754079234240230092590070173196036225475647894064754834664776041146323390565134330684495397907090302346046147096169688688501408347040546074295869913829668246818571031887906528703665083243197440477185567893482308943106828702722809736248093996270607472645539925399442808113736943388729406307926159599546262462970706259484556903471197299640908941805953439325123623550813494900436427852713831591256898929519642728757394691427253436694153236100453730488198551706594121735246258954873016760029886592578662856124966552353382942878542534048308330701653722856355915253478445981831341129001999205981352205117336585640782648494276441137639386692480311836445369858917544264739988228462184490087776977631279572267265556259628254276531830013407092233436577916012809317940171859859993384923549564005709955856113498025249906698423301735035804408116855265311709957089942732870925848789443646005041089226691783525870785951298344172953519537885534573742608590290817651557803905946408735061232261120093731080485485263572282576820341605048466277504500312620080079980492548534694146977516493270950493463938243222718851597405470214828971117779237612257887347718819682546298126868581705074027255026332904497627789442362167411918626943965067151577958675648239939176042601763387045499017614364120469218237076488783419689686118155815873606293860381017121585527266830082383404656475880405138080163363887421637140643549556186896411228214075330265510042410489678352858829024367090488711819090949453314421828766181031007354770549815968077200947469613436092861484941785017180779306810854690009445899527942439813921350558642219648349151263901280383200109773868066287792397180146134324457264009737425700735921003154150893679300816998053652027600727749674584002836240534603726341655425902760183484030681138185510597970566400750942608788573579603732451414678670368809880609716425849759513806930944940151542222194329130217391253835591503100333032511174915696917450271494331515588540392216409722910112903552181576282328318234254832611191280092825256190205263016391147724733148573910777587442538761174657867116941477642144111126358355387136101102326798775641024682403226483464176636980663785768134920453022408197278564719839630878154322116691224641591177673225326433568614618654522268126887268445968442416107854016768142080885028005414361314623082102594173756238994207571362751674573189189456283525704413354375857534269869947254703165661399199968262824727064133622217892390317608542894373393561889165125042440400895271983787386480584726895462438823437517885201439560057104811949884239060613695734231559079670346149143447886360410318235073650277859089757827273130504889398900992391350337325085598265586708924261242947367019390772713070686917092646254842324074855036608013604668951184009366860954632500214585293095000090715105823626729326453738210493872499669933942468551648326113414611068026744663733437534076429402668297386522093570162638464852851490362932019919968828517183953669134522244470804592396602817156551565666111359823112250628905854914509715755390024393153519090210711945730024388017661503527086260253788179751947806101371500448991721002220133501310601639154158957803711779277522597874289191791552241718958536168059474123419339842021874564925644346239253195313510331147639491199507285843065836193536932969928983791494193940608572486396883690326556436421664425760791471086998431573374964883529276932822076294728238153740996154559879825989109371712621828302584811238901196822142945766758071865380650648702613389282299497257453033283896381843944770779402284359883410035838542389735424395647555684095224844554139239410001620769363684677641301781965937997155746854194633489374843912974239143365936041003523437770658886778113949861647874714079326385873862473288964564359877466763847946650407411182565837887845485814896296127399841344272608606187245545236064315371011274680977870446409475828034876975894832824123929296058294861919667091895808983320121031843034012849511620353428014412761728583024355983003204202451207287253558119584014918096925339507577840006746552603144616705082768277222353419110263416315714740612385042584598841990761128725805911393568960143166828317632356732541707342081733223046298799280490851409479036887868789493054695570307261900950207643349335910602454508645362893545686295853131533718386826561786227363716975774183023986006591481616404944965011732131389574706208847480236537103115089842799275442685327797431139514357417221975979935968525228574526379628961269157235798662057340837576687388426640599099350500081337543245463596750484423528487470144354541957625847356421619813407346854111766883118654489377697956651727966232671481033864391375186594673002443450054499539974237232871249483470604406347160632583064982979551010954183623503030945309733583446283947630477564501500850757894954893139394489921612552559770143685894358587752637962559708167764380012543650237141278346792610199558522471722017772370041780841942394872540680155603599839054898572354674564239058585021671903139526294455439131663134530893906204678438778505423939052473136201294769187497519101147231528932677253391814660730008902776896311481090220972452075916729700785058071718638105496797310016787085069420709223290807038326345345203802786099055690013413718236837099194951648960075504934126787643674638490206396401976668559233565463913836318574569814719621084108096188460545603903845534372914144651347494078488442377217515433426030669883176833100113310869042193903108014378433415137092435301367763108491351615642269847507430329716746964066653152703532546711266752246055119958183196376370761799191920357958200759560530234626775794393630746305690108011494271410093913691381072581378135789400559950018354251184172136055727522103526803735726527922417373605751127887218190844900617801388971077082293100279766593583875890939568814856026322439372656247277603789081445883785501970284377936240782505270487581647032458129087839523245323789602984166922548964971560698119218658492677040395648127810217991321741630581055459880130048456299765112124153637451500563507012781592671424134210330156616535602473380784302865525722275304999883701534879300806260180962381516136690334111138653851091936739383522934588832255088706450753947395204396807906708680644509698654880168287434378612645381583428075306184548590379821799459968115441974253634439960290251001588827216474500682070419376158454712318346007262933955054823955713725684023226821301247679452264482091023564775272308208106351889915269288910845557112660396503439789627825001611015323516051965590421184494990778999200732947690586857787872098290135295661397888486050978608595701773129815531495168146717695976099421003618355913877781769845875810446628399880600616229848616935337386578773598336161338413385368421197893890018529569196780455448285848370117096721253533875862158231013310387766827211572694951817958975469399264219791552338576623167627547570354699414892904130186386119439196283887054367774322427680913236544948536676800000106526248547305586159899914017076983854831887501429389089950685453076511680333732226517566220752695179144225280816517166776672793035485154204023817460892328391703275425750867655117859395002793389592057668278967764453184040418554010435134838953120132637836928358082719378312654961745997056745071833206503455664403449045362756001125018433560736122276594927839370647842645676338818807565612168960504161139039063960162022153684941092605387688714837989559999112099164646441191856827700457424343402167227644558933012778158686952506949936461017568506016714535431581480105458860564550133203758645485840324029871709348091055621167154684847780394475697980426318099175642280987399876697323769573701580806822904599212366168902596273043067931653114940176473769387351409336183321614280214976339918983548487562529875242387307755955595546519639440182184099841248982623673771467226061633643296406335728107078875816404381485018841143188598827694490119321296827158884133869434682859006664080631407775772570563072940049294030242049841656547973670548558044586572022763784046682337985282710578431975354179501134727362577408021347682604502285157979579764746702284099956160156910890384582450267926594205550395879229818526480070683765041836562094555434613513415257006597488191634135955671964965403218727160264859304903978748958906612725079482827693895352175362185079629778514618843271922322381015874445052866523802253284389137527384589238442253547265309817157844783421582232702069028723233005386216347988509469547200479523112015043293226628272763217790884008786148022147537657810581970222630971749507212724847947816957296142365859578209083073323356034846531873029302665964501371837542889755797144992465403868179921389346924474198509733462679332107268687076806263991936196504409954216762784091466985692571507431574079380532392523947755744159184582156251819215523370960748332923492103451462643744980559610330799414534778457469999212859999939961228161521931488876938802228108300198601654941654261696858678837260958774567618250727599295089318052187292461086763995891614585505839727420980909781729323930106766386824040111304024700735085782872462713494636853181546969046696869392547251941399291465242385776255004748529547681479546700705034799958886769501612497228204030399546327883069597624936151010243655535223069061294938859901573466102371223547891129254769617600504797492806072126803922691102777226102544149221576504508120677173571202718024296810620377657883716690910941807448781404907551782038565390991047759414132154328440625030180275716965082096427348414695726397884256008453121406593580904127113592004197598513625479616063228873618136737324450607924411763997597461938358457491598809766744709300654634242346063423747466608043170126005205592849369594143408146852981505394717890045183575515412522359059068726487863575254191128887737176637486027660634960353679470269232297186832771739323619200777452212624751869833495151019864269887847171939664976907082521742336566272592844062043021411371992278526998469884770232382384005565551788908766136013047709843861168705231055314916251728373272867600724817298763756981633541507460883866364069347043720668865127568826614973078865701568501691864748854167915459650723428773069985371390430026653078398776385032381821553559732353068604301067576083890862704984188859513809103042359578249514398859011318583584066747237029714978508414585308578133915627076035639076394731145549583226694570249413983163433237897595568085683629725386791327505554252449194358912840504522695381217913191451350099384631177401797151228378546011603595540286440590249646693070776905548102885020808580087811577381719174177601733073855475800605601433774329901272867725304318251975791679296996504146070664571258883469797964293162296552016879730003564630457930884032748077181155533090988702550520768046303460865816539487695196004408482065967379473168086415645650530049881616490578831154345485052660069823093157776500378070466126470602145750579327096204782561524714591896522360839664562410519551052235723973951288181640597859142791481654263289200428160913693777372229998332708208296995573772737566761552711392258805520189887620114168005468736558063347160373429170390798639652296131280178267971728982293607028806908776866059325274637840539769184808204102194471971386925608416245112398062011318454124478205011079876071715568315407886543904121087303240201068534194723047666672174986986854707678120512473679247919315085644477537985379973223445612278584329684664751333657369238720146472367942787004250325558992688434959287612400755875694641370562514001179713316620715371543600687647731867558714878398908107429530941060596944315847753970094398839491443235366853920994687964506653398573888786614762944341401049888993160051207678103588611660202961193639682134960750111649832785635316145168457695687109002999769841263266502347716728657378579085746646077228341540311441529418804782543876177079043000156698677679576090996693607559496515273634981189641304331166277471233881740603731743970540670310967676574869535878967003192586625941051053358438465602339179674926784476370847497833365557900738419147319886271352595462518160434225372996286326749682405806029642114638643686422472488728343417044157348248183330164056695966886676956349141632842641497453334999948000266998758881593507357815195889900539512085351035726137364034367534714104836017546488300407846416745216737190483109676711344349481926268111073994825060739495073503169019731852119552635632584339099822498624067031076831844660729124874754031617969941139738776589986855417031884778867592902607004321266617919223520938227878880988633599116081923535557046463491132085918979613279131975649097600013996234445535014346426860464495862476909434704829329414041114654092398834443515913320107739441118407410768498106634724104823935827401944935665161088463125678529776973468430306146241803585293315973458303845541033701091676776374276210213701354854450926307190114731848574923318167207213727935567952844392548156091372812840633303937356242001604566455741458816605216660873874804724339121295587776390696903707882852775389405246075849623157436917113176134783882719416860662572103685132156647800147675231039357860689611125996028183930954870905907386135191459181951029732787557104972901148717189718004696169777001791391961379141716270701895846921434369676292745910994006008498356842520191559370370101104974733949387788598941743303178534870760322198297057975119144051099423588303454635349234982688362404332726741554030161950568065418093940998202060999414021689090070821330723089662119775530665918814119157783627292746156185710372172471009521423696483086410259288745799932237495519122195190342445230753513380685680735446499512720317448719540397610730806026990625807602029273145525207807991418429063884437349968145827337207266391767020118300464819000241308350884658415214899127610651374153943565721139032857491876909441370209051703148777346165287984823533829726013611098451484182380812054099612527458088109948697221612852489742555551607637167505489617301680961380381191436114399210638005083214098760459930932485102516829446726066613815174571255975495358023998314698220361338082849935670557552471290274539776214049318201465800802156653606776550878380430413431059180460680083459113664083488740800574127258670479225831912741573908091438313845642415094084913391809684025116399193685322555733896695374902662092326131885589158083245557194845387562878612885900410600607374650140262782402734696252821717494158233174923968353013617865367376064216677813773995100658952887742766263684183068019080460984980946976366733566228291513235278880615776827815958866918023894033307644191240341202231636857786035727694154177882643523813190502808701857504704631293335375728538660588890458311145077394293520199432197117164223500564404297989208159430716701985746927384865383343614579463417592257389858800169801475742054299580124295810545651083104629728293758416116253256251657249807849209989799062003593650993472158296517413579849104711166079158743698654122234834188772292944633517865385673196255985202607294767407261676714557364981210567771689348491766077170527718760119990814411305864557791052568430481144026193840232247093924980293355073184589035539713308844617410795916251171486487446861124760542867343670904667846867027409188101424971114965781772427934707021668829561087779440504843752844337510882826477197854000650970403302186255614733211777117441335028160884035178145254196432030957601869464908868154528562134698835544456024955666843660292219512483091060537720198021831010327041783866544718126039719068846237085751808003532704718565949947612424811099928867915896904956394762460842406593094862150769031498702067353384834955083636601784877106080980426924713241000946401437360326564518456679245666955100150229833079849607994988249706172367449361226222961790814311414660941234159359309585407913908720832273354957208075716517187659944985693795623875551617575438091780528029464200447215396280746360211329425591600257073562812638733106005891065245708024474937543184149401482119996276453106800663118382376163966318093144467129861552759820145141027560068929750246304017351489194576360789352855505317331416457050499644389093630843874484783961684051845273288403234520247056851646571647713932377551729479512613239822960239454857975458651745878771331813875295980941217422730035229650808917770506825924882232215493804837145478164721397682096332050830564792048208592047549985732038887639160199524091893894557676874973085695595801065952650303626615975066222508406742889826590751063756356996821151094966974458054728869363102036782325018232370845979011154847208761821247781326633041207621658731297081123075815982124863980721240786887811450165582513617890307086087019897588980745664395515741536319319198107057533663373803827215279884935039748001589051942087971130805123393322190346624991716915094854140187106035460379464337900589095772118080446574396280618671786101715674096766208029576657705129120990794430463289294730615951043090222143937184956063405618934251305726829146578329334052463502892917547087256484260034962961165413823007731332729830500160256724014185152041890701154288579920812198449315699905918201181973350012618772803681248199587707020753240636125931343859554254778196114293516356122349666152261473539967405158499860355295332924575238881013620234762466905581643896786309762736550472434864307121849437348530060638764456627218666170123812771562137974614986132874411771455244470899714452288566294244023018479120547849857452163469644897389206240194351831008828348024924908540307786387516591130287395878709810077271827187452901397283661484214287170553179654307650453432460053636147261818096997693348626407743519992868632383508875668359509726557481543194019557685043724800102041374983187225967738715495839971844490727914196584593008394263702087563539821696205532480321226749891140267852859967340524203109179789990571882194939132075343170798002373659098537552023891164346718558290685371189795262623449248339249634244971465684659124891855662958932990903523923333364743520370770101084388003290759834217018554228386161721041760301164591878053936744747205998502358289183369292233732399948043710841965947316265482574809948250999183300697656936715968936449334886474421350084070066088359723503953234017958255703601693699098867113210979889707051728075585519126993067309925070407024556850778679069476612629808225163313639952117098452809263037592242674257559989289278370474445218936320348941552104459726188380030067761793138139916205806270165102445886924764924689192461212531027573139084047000714356136231699237169484813255420091453041037135453296620639210547982439212517254013231490274058589206321758949434548906846399313757091034633271415316223280552297297953801880162859073572955416278867649827418616421878988574107164906919185116281528548679417363890665388576422915834250067361245384916067413734017357277995634104332688356950781493137800736235418007061918026732855119194267609122103598746924117283749312616339500123959924050845437569850795704622266461900010350049018303415354584283376437811198855631877779253720116671853954183598443830520376281944076159410682071697030228515225057312609304689842343315273213136121658280807521263154773060442377475350595228717440266638914881717308643611138906942027908814311944879941715404210341219084709408025402393294294549387864023051292711909751353600092197110541209668311151632870542302847007312065803262641711616595761327235156666253667271899853419989523688483099930275741991646384142707798870887422927705389122717248632202889842512528721782603050099451082478357290569198855546788607946280537122704246654319214528176074148240382783582971930101788834567416781139895475044833931468963076339665722672704339321674542182455706252479721997866854279897799233957905758189062252547358220523642485078340711014498047872669199018643882293230538231855973286978092225352959101734140733488476100556401824239219269506208318381454698392366461363989101210217709597670490830508185470419466437131229969235889538493013635657618610606222870559942337163102127845744646398973818856674626087948201864748767272722206267646533809980196688368099415907577685263986514625333631245053640261056960551318381317426118442018908885319635698696279503673842431301133175330532980201668881748134298868158557781034323175306478498321062971842518438553442762012823457071698853051832617964117857960888815032960229070561447622091509473903594664691623539680920139457817589108893199211226007392814916948161527384273626429809823406320024402449589445612916704950823581248739179964864113348032475777521970893277226234948601504665268143987705161531702669692970492831628550421289814670619533197026950721437823047687528028735412616639170824592517001071418085480063692325946201900227808740985977192180515853214739265325155903541020928466592529991435379182531454529059841581763705892790690989691116438118780943537152133226144362531449012745477269573939348154691631162492887357471882407150399500944673195431619385548520766573882513963916357672315100555603726339486720820780865373494244011579966750736071115935133195919712094896471755302453136477094209463569698222667377520994516845064362382421185353488798939567318780660610788544000550827657030558744854180577889171920788142335113866292966717964346876007704799953788338787034871802184243734211227394025571769081960309201824018842705704609262256417837526526335832424066125331152942345796556950250681001831090041124537901533296615697052237921032570693705109083078947999900499939532215362274847660361367769797856738658467093667958858378879562594646489137665219958828693380183601193236857855855819555604215625088365020332202451376215820461810670519533065306060650105488716724537794283133887163139559690583208341689847606560711834713621812324622725884199028614208728495687963932546428534307530110528571382964370999035694888528519040295604734613113826387889755178856042499874831638280404684861893818959054203988987265069762020199554841265000539442820393012748163815853039643992547020167275932857436666164411096256633730540921951967514832873480895747777527834422109107311135182804603634719818565557295714474768255285786334934285842311874944000322969069775831590385803935352135886007960034209754739229673331064939560181223781285458431760556173386112673478074585067606304822940965304111830667108189303110887172816751957967534718853722930961614320400638132246584111115775835858113501856904781536893813771847281475199835050478129771859908470762197460588742325699582889253504193795826061621184236876851141831606831586799460165205774052942305360178031335726326705479033840125730591233960188013782542192709476733719198728738524805742124892118347087662966720727232565056512933312605950577772754247124164831283298207236175057467387012820957554430596839555568686118839713552208445285264008125202766555767749596962661260456524568408613923826576858338469849977872670655519185446869846947849573462260629421962455708537127277652309895545019303773216664918257815467729200521266714346320963789185232321501897612603437368406719419303774688099929687758244104787812326625318184596045385354383911449677531286426092521153767325886672260404252349108702695809964759580579466397341906401003636190404203311357933654242630356145700901124480089002080147805660371015412232889146572239314507607167064355682743774396578906797268743847307634645167756210309860409271709095128086309029738504452718289274968921210667008164858339553773591913695015316201890888748421079870689911480466927065094076204650277252865072890532854856143316081269300569378541786109696920253886503457718317668688592368148847527649846882194973972970773718718840041432312763650481453112285099002074240925585925292610302106736815434701525234878635164397623586041919412969769040526483234700991115424260127343802208933109668636789869497799400126016422760926082349304118064382913834735467972539926233879158299848645927173405922562074910530853153718291168163721939518870095778818158685046450769934394098743351443162633031724774748689791820923948083314397084067308407958935810896656477585990556376952523265361442478023082681183103773588708924061303133647737101162821461466167940409051861526036009252194721889091810733587196414214447865489952858234394705007983038853886083103571930600277119455802191194289992272235345870756624692617766317885514435021828702668561066500353105021631820601760921798468493686316129372795187307897263735371715025637873357977180818487845886650433582437700414771041493492743845758710715973155943942641257027096512510811554824793940359768118811728247215825010949609662539339538092219559191818855267806214992317276316321833989693807561685591175299845013206712939240414459386239880938124045219148483164621014738918251010909677386906640415897361047643650006807710565671848628149637111883219244566394581449148616550049567698269030891118568798692947051352481609174324301538368470729289898284602223730145265567989862776796809146979837826876431159883210904371561129976652153963546442086919756737000573876497843768628768179249746943842746525631632300555130417422734164645512781278457777245752038654375428282567141288583454443513256205446424101103795546419058116862305964476958705407214198521210673433241075676757581845699069304604752277016700568454396923404171108988899341635058515788735343081552081177207188037910404698306957868547393765643363197978680367187307969392423632144845035477631567025539006542311792015346497792906624150832885839529054263768766896880503331722780018588506973623240389470047189761934734430843744375992503417880797223585913424581314404984770173236169471976571535319775499716278566311904691260918259124989036765417697990362375528652637573376352696934435440047306719886890196814742876779086697968852250163694985673021752313252926537589641517147955953878427849986645630287883196209983049451987439636907068276265748581043911223261879405994155406327013198989570376110532360629867480377915376751158304320849872092028092975264981256916342500052290887264692528466610466539217148208013050229805263783642695973370705392278915351056888393811324975707133102950443034671598944878684711643832805069250776627450012200352620370946602341464899839025258883014867816219677519458316771876275720050543979441245990077115205154619930509838698254284640725554092740313257163264079293418334214709041254253352324802193227707535554679587163835875018159338717423606155117101312352563348582036514614187004920570437201826173319471570086757853933607862273955818579758725874410254207710547536129404746010009409544495966288148691590389907186598056361713769222729076419775517772010427649694961105622059250242021770426962215495872645398922769766031052498085575947163107587013320886146326641259114863388122028444069416948826152957762532501987035987067438046982194205638125583343642194923227593722128905642094308235254408411086454536940496927149400331978286131818618881111840825786592875742638445005994422956858646048103301538891149948693543603022181094346676400002236255057363129462629609619876056425996394613869233083719626595473923462413459779574852464783798079569319865081597767535055391899115133525229873611277918274854200868953965835942196333150286956119201229888988700607999279541118826902307891310760361763477948943203210277335941690865007193280401716384064498787175375678118532132840821657110754952829497493621460821558320568723218557406516109627487437509809223021160998263303391546949464449100451528092508974507489676032409076898365294065792019831526541065813682379198409064571246894847020935776119313998024681340520039478194986620262400890215016616381353838151503773502296607462795291038406868556907015751662419298724448271942933100485482445458071889763300323252582158128032746796200281476243182862217105435289834820827345168018613171959332471107466222850871066611770346535283957762599774467218571581612641114327179434788599089280848669491413909771673690027775850268664654056595039486784111079011610400857274456293842549416759460548711723594642910585090995021495879311219613590831588262068233215615308683373083817327932819698387508708348388046388478441884003184712697454370937329836240287519792080232187874488287284372737801782700805878241074935751488997891173974612932035108143270325140903048746226294234432757126008664250833318768865075642927160552528954492153765175149219636718104943531785838345386525565664065725136357506435323650893679043170259787817719031486796384082881020946149007971513771709906195496964007086766710233004867263147551053723175711432231741141168062286420638890621019235522354671166213749969326932173704310598722503945657492461697826097025335947502091383667377289443869640002811034402608471289900074680776484408871134135250336787731679770937277868216611786534423173226463784769787514433209534000165069213054647689098505020301504488083426184520873053097318949291642532293361243151430657826407028389840984160295030924189712097160164926561341343342229882790992178604267981245728534580133826099587717811310216734025656274400729683406619848067661580502169183372368039902793160642043681207990031626444914619021945822969099212278855394878353830564686488165556229431567312827439082645061162894280350166133669782405177015521962652272545585073864058529983037918035043287670380925216790757120406123759632768567484507915114731344000183257034492090971243580944790046249431345502890068064870429353403743603262582053579011839564908935434510134296961754524957396062149028872893279252069653538639644322538832752249960598697475988232991626354597332444516375533437749292899058117578635555562693742691094711700216541171821975051983178713710605106379555858890556885288798908475091576463907469361988150781468526213325247383765119299015610918977792200870579339646382749068069876916819749236562422608715417610043060890437797667851966189140414492527048088197149880154205778700652159400928977760133075684796699295543365613984773806039436889588764605498387147896848280538470173087111776115966350503997934386933911978988710915654170913308260764740630571141109883938809548143782847452883836807941888434266622207043872288741394780101772139228191199236540551639589347426395382482960903690028835932774585506080131798840716244656399794827578365019551422155133928197822698427863839167971509126241054872570092407004548848569295044811073808799654748156891393538094347455697212891982717702076661360248958146811913361412125878389557735719498631721084439890142394849665925173138817160266326193106536653504147307080441493916936326237376777709585031325599009576273195730864804246770121232702053374266705314244820816813030639737873664248367253983748769098060218278578621651273856351329014890350988327061725893257536399397905572917516009761545904477169226580631511102803843601737474215247608515209901615858231257159073342173657626714239047827958728150509563309280266845893764964977023297364131906098274063353108979246424213458374090116939196425045912881340349881063540088759682005440836438651661788055760895689672753153808194207733259791727843762566118431989102500749182908647514979400316070384554946538594602745244746681231468794344161099333890899263841184742525704457251745932573898956518571657596148126602031079762825416559050604247911401695790033835657486925280074302562341949828646791447632277400552946090394017753633565547193100017543004750471914489984104001586794617924161001645471655133707407395026044276953855383439755054887109978520540117516974758134492607943368954378322117245068734423198987884412854206474280973562580706698310697993526069339213568588139121480735472846322778490808700246777630360555123238665629517885371967303463470122293958160679250915321748903084088651606111901149844341235012464692802880599613428351188471544977127847336176628506216977871774382436256571177945006447771837022199910669502165675764404499794076503799995484500271066598781360380231412683690578319046079276529727769404361302305178708054651154246939526512710105292707030667302444712597393995051462840476743136373997825918454117641332790646063658415292701903027601733947486696034869497654175242930604072700505903950314852292139257559484507886797792525393176515641619716844352436979444735596426063339105512682606159572621703669850647328126672452198906054988028078288142979633669674412480598219214633956574572210229867759974673812606936706913408155941201611596019023775352555630060624798326124988128819293734347686268921923977783391073310658825681377717232831532908252509273304785072497713944833389255208117560845296659055394096556854170600117985729381399825831929367910039184409928657560599359891000296986446097471471847010153128376263114677420914557404181590880006494323785583930853082830547607679952435739163122188605754967383224319565065546085288120190236364471270374863442172725787950342848631294491631847534753143504139209610879605773098720135248407505763719925365047090858251393686346386336804289176710760211115982887553994012007601394703366179371539630613986365549221374159790511908358829009765664730073387931467891318146510931676157582135142486044229244530411316065270097433008849903467540551864067734260358340960860553374736276093565885310976099423834738222208729246449768456057956251676557408841032173134562773585605235823638953203853402484227337163912397321599544082842166663602329654569470357718487344203422770665383738750616921276801576618109542009770836360436111059240911788954033802142652394892968643980892611463541457153519434285072135345301831587562827573389826889852355779929572764522939156747756667605108788764845349363606827805056462281359888587925994094644604170520447004631513797543173718775603981596264750141090665886616218003826698996196558058720863972117699521946678985701179833244060181157565807428418291061519391763005919431443460515404771057005433900018245311773371895585760360718286050635647997900413976180895536366960316219311325022385179167205518065926351803625121457592623836934822266589557699466049193811248660909979812857182349400661555219611220720309227764620099931524427358948871057662389469388944649509396033045434084210246240104872332875008174917987554387938738143989423801176270083719605309438394006375611645856094312951759771393539607432279248922126704580818331376416581826956210587289244774003594700926866265965142205063007859200248829186083974373235384908396432614700053242354064704208949921025040472678105908364400746638002087012666420945718170294675227854007450855237772089058168391844659282941701828823301497155423523591177481862859296760504820386434310877956289292540563894662194826871104282816389397571175778691543016505860296521745958198887868040811032843273986719862130620555985526603640504628215230615459447448990883908199973874745296981077620148713400012253552224669540931521311533791579802697955571050850747387475075806876537644578252443263804614304288923593485296105826938210349800040524840708440356116781717051281337880570564345061611933042444079826037795119854869455915205196009304127100727784930155503889536033826192934379708187432094991415959339636811062755729527800425486306005452383915106899891357882001941178653568214911852820785213012551851849371150342215954224451190020739353962740020811046553020793286725474054365271759589350071633607632161472581540764205302004534018357233829266191530835409512022632916505442612361919705161383935732669376015691442994494374485680977569630312958871916112929468188493633864739274760122696415884890096571708616059814720446742866420876533479985822209061980217321161423041947775499073873856794118982466091309169177227420723336763503267834058630193019324299639720444517928812285447821195353089891012534297552472763573022628138209180743974867145359077863353016082155991131414420509144729353502223081719366350934686585865631485557586244781862010871188976065296989926932817870557643514338206014107732926106343152533718224338526352021773544071528189813769875515757454693972715048846979361950047772097056179391382898984532742622728864710888327017372325881824465843624958059256033810521560620615571329915608489206434030339526226345145428367869828807425142256745180618414956468611163540497189768215422772247947403357152743681940989205011365340012384671429655186734415374161504256325671343024765512521921803578016924032669954174608759240920700466934039651017813485783569444076047023254075555776472845075182689041829396611331016013111907739863246277821902365066037404160672496249013743321724645409741299557052914243820807609836482346597388669134991978401310801558134397919485283043673901248208244481412809544377389832005986490915950532285791457688496257866588599917986752055455809900455646117875524937012455321717019428288461740273664997847550829422802023290122163010230977215156944642790980219082668986883426307160920791408519769523555348865774342527753119724743087304361951139611908003025587838764420608504473063129927788894272918972716989057592524467966018970748296094919064876469370275077386643239191904225429023531892337729316673608699622803255718530891928440380507103006477684786324319100022392978525537237556621364474009676053943983823576460699246526008909062410590421545392790441152958034533450025624410100635953003959886446616959562635187806068851372346270799732723313469397145628554261546765063246567662027924520858134771760852169134094652030767339184114750414016892412131982688156866456148538028753933116023229255561894104299533564009578649534093511526645402441877594931693056044868642086275720117231952640502309977456764783848897346431721598062678767183800524769688408498918508614900343240347674268624595239589035858213500645099817824463608731775437885967767291952611121385919472545140030118050343787527766440276261894101757687268042817662386068047788524288743025914524707395054652513533945959878961977891104189029294381856720507096460626354173294464957661265195349570186001541262396228641389779673332907056737696215649818450684226369036784955597002607986799626101903933126376855696876702929537116252800554310078640872893922571451248113577862766490242516199027747109033593330930494838059785662884478744146984149906712376478958226329490467981208998485716357108783119184863025450162092980582920833481363840542172005612198935366937133673339246441612522319694347120641737549121635700857369439730597970971972666664226743111776217640306868131035189911227133972403688700099686292254646500638528862039380050477827691283560337254825579391298525150682996910775425764748832534141213280062671709400909822352965795799780301828242849022147074811112401860761341515038756983091865278065889668236252393784527263453042041880250844236319038331838455052236799235775292910692504326144695010986108889991465855188187358252816430252093928525807796973762084563748211443398816271003170315133440230952635192958868069082135585368016100021374085115448491268584126869589917414913382057849280069825519574020181810564129725083607035685105533178784082900004155251186577945396331753853209214972052660783126028196116485809868458752512999740409279768317663991465538610893758795221497173172813151793290443112181587102351874075722210012376872194474720934931232410706508061856237252673254073332487575448296757345001932190219911996079798937338367324257610393898534927877747398050808001554476406105352220232540944356771879456543040673589649101761077594836454082348613025471847648518957583667439979150851285802060782055446299172320202822291488695939972997429747115537185892423849385585859540743810488262464878805330427146301194158989632879267832732245610385219701113046658710050008328517731177648973523092666123458887310288351562644602367199664455472760831011878838915114934093934475007302585581475619088139875235781233134227986650352272536717123075686104500454897036007956982762639234410714658489578024140815840522953693749971066559489445924628661996355635065262340533943914211127181069105229002465742360413009369188925586578466846121567955425660541600507127664176605687427420032957716064344860620123982169827172319782681662824993871499544913730205184366907672357740005393266262276032365975171892590180110429038427418550789488743883270306328327996300720069801224436511639408692222074532024462412115580435454206421512158505689615735641431306888344318528085397592773443365538418834030351782294625370201578215737326552318576355409895403323638231921989217117744946940367829618592080340386757583411151882417743914507736638407188048935825686854201164503135763335550944031923672034865101056104987272647213198654343545040913185951314518127643731043897250700498198705217627249406521461995923214231443977654670835171474936798618655279171582408065106379950018429593879915835017158075988378496225739851212981032637937621832245659423668537679911314010804313973233544909082491049914332584329882103398469814171575601082970658306521134707680368069532297199059990445120908727577622535104090239288877942463048328031913271049547859918019696783532146444118926063152661816744319355081708187547705080265402529410921826485821385752668815558411319856002213515888721036569608751506318753300294211868222189377554602722729129050429225978771066787384000061677215463844129237119352182849982435092089180168557279815642185819119749098573057033266764646072875743056537260276898237325974508447964954564803077159815395582777913937360171742299602735310276871944944491793978514463159731443535185049141394155732938204854212350817391254974981930871439661513294204591938010623142177419918406018034794988769105155790555480695387854006645337598186284641990522045280330626369562649091082762711590385699505124652999606285544383833032763859980079292284665950355121124528408751622906026201185777531374794936205549640107300134885315073548735390560290893352640071327473262196031177343394367338575912450814933573691166454128178817145402305475066713651825828489809951213919399563324133655677709800308191027204099714868741813466700609405102146269028044915964654533010775469541308871416531254481306119240782118869005602778182423502269618934435254763357353648561936325441775661398170393063287216690572225974520919291726219984440964615826945638023950283712168644656178523556516412771282691868861557271620147493405227694659571219831494338162211400693630743044417328478610177774383797703723179525543410722344551255558999864618387676490397246116795901810003509892864120419516355110876320426761297982652942588295114127584126273279079880755975185157684126474220947972184330935297266521001566251455299474512763155091763673025946213293019040283795424632325855030109670692272022707486341900543830265068121414213505715417505750863990767394633514620908288893493837643939925690060406731142209331219593620298297235116325938677224147791162957278075239505625158160313335938231150051862689053065836812998810866326327198061127154885879809348791291370749823057592909186293919501472119758606727009254771802575033773079939713453953264619526999659638565491759045833358579910201271320458390320085387888163363768518208372788513117522776960978796214237216254521459128183179821604411131167140691482717098101545778193920231156387195080502467972579249760577262591332855972637121120190572077140914864507409492671803581515757151405039761096384675556929897038354731410022380258346876735012977541327953206097115450648421218593649099791776687477448188287063231551586503289816422828823274686610659273219790716238464215348985247621678905026099804526648392954235728734397768049577409144953839157556548545905897649519851380100795801078375994577529919670054760225255203445398871253878017196071816407812484784725791240782454436168234523957068951427226975043187363326301110305342333582160933319121880660826834142891041517324721605335584999322454873077882290525232423486153152097693846104258284971496347534183756200301491570327968530186863157248840152663983568956363465743532178349319982554211730846774529708583950761645822963032442432823773745051702856069806788952176819815671078163340526675953942492628075696832610749532339053622309080708145591983735537774874202903901814293731152933464446815121294509759653430628421531944572711861490001765055817709530246887526325011970520947615941676872778447200019278913725184162285778379228443908430118112149636642465903363419454065718354477191244662125939265662030688852005559912123536371822692253178145879259375044144893398160865790087616502463519704582889548179375668104647461410514249887025213993687050937230544773411264135489280684105910771667782123833281026218558775131272117934444820144042574508306394473836379390628300897330624138061458941422769474793166571762318247216835067807648757342049155762821758397297513447899069658953254894033561561316740327647246921250575911625152965456854463349811431767025729566184477548746937846423373723898192066204851189437886822480727935202250179654534375727416391079197295295081294292220534771730418447791567399173841831171036252439571615271466900581470000263301045264354786590329073320546833887207873544476264792529769017091200787418373673508771337697768349634425241994995138831507487753743384945825976556099655595431804092017849718468549737069621208852437701385375768141663272241263442398215294164537800049250726276515078908507126599703670872669276430837722968598516912230503746274431085293430527307886528397733524601746352770320593817912539691562106363762588293757137384075440646896478310070458061344673127159119460843593582598778283526653115106504162329532904777217408355934972375855213804830509000964667608830154061282430874064559443185341375522016630581211103345312074508682433943215904359443031243122747138584203039010607094031523555617276799416002039397509989762933532585557562480899669182986422267750236019325797472674257821111973470940235745722227121252685238429587427350156366009318804549333898974157149054418255973808087156528143010267046028431681923039253529779576586241439270154974087927313105163611913757700892956482332364829826302460797587576774537716010249080462430185652416175665560016085912153455626760219268998285537787258314514408265458348440947846317877737479465358016996077940556870119232860804113090462935087182712593466871276669487389982459852778649956916546402945893506496433580982476596516514209098675520380830920323048734270346828875160407154665383461961122301375945157925269674364253192739003603860823645076269882749761872357547676288995075211480485252795084503395857083813047693788132112367428131948795022806632017002246033198967197064916374117585485187848401205484467258885140156272501982171906696081262778548596481836962141072171421498636191877475450965030895709947093433785698167446582826791194061195603784539785583924076127634410576675102430755981455278616781594965706255975507430652108530159790807334373607943286675789053348366955548680391343372015649883422089339997164147974693869690548008919306713805717150585730714881564992071408675825960287605645978242377024246980532805663278704192676846711626687946348695046450742021937394525926266861355294062478136120620263649819999949840514386828525895634226432870766329930489172340072547176418868535137233266787792173834754148002280339299735793615241275582956927683723123479898944627433045456679006203242051639628258844308543830720149567210646053323853720314324211260742448584509458049408182092763914000854042202355626021856434899414543995041098059181794888262805206644108631900168856815516922948620301073889718100770929059048074909242714101893354281842999598816966099383696164438152887721408526808875748829325873580990567075581701794916190611400190855374488272620093668560447559655747648567400817738170330738030547697360978654385938218722058390234444350886749986650604064587434600533182743629617786251808189314436325120510709469081358644051922951293245007883339878842933934243512634336520438581291283434529730865290978330067126179813031679438553572629699874035957045845223085639009891317947594875212639707837594486113945196028675121056163897600888009274611586080020780334159145179707303683519697776607637378533301202412011204698860920933908536577322239241244905153278095095586645947763448226998607481329730263097502881210351772312446509534965369309001863776409409434983731325132186208021480992268550294845466181471555744470966953017769043427203189277060471778452793916047228153437980353967986142437095668322149146543801459382927739339603275404800955223181666738035718393275707714204672383862461780397629237713120958078936384144792980258806552212926209362393063731349664018661951081158347117331202580586672763999276357907806381881306915636627412543125958993611964762610140556350339952314032311381965623632719896183725484533370206256346422395276694356837676136871196292181875457608161705303159072882870071231366630872275491866139577373054606599743781098764980241401124214277366808275139095931340415582626678951084677611866595766016599817808941498575497628438785610026379654317831363402513581416115190209649913354873313111502270068193013592959597164019719605362503355847998096348871803911161281359596856547886832585643789617315976200241962155289629790481982219946226948713746244472909345647002853769495885959160678928249105441251599630078136836749020937491573289627002865682934443134234735123929825916673950342599586897069726733258273590312128874666045146148785034614282776599160809039865257571726308183349444182019353338507129234577437557934406217871133006310600332405399169368260374617663856575887758020122936635327026710068126182517291460820254189288593524449107013820621155382779356529691457650204864328286555793470720963480737269214118689546732276775133569019015372366903686538916129168888787640752549349424973342718117889275993159671935475898809792452526236365903632007085444078454479734829180208204492667063442043755532505052752283377888704080403353192340768563010934777212563908864041310107381785333831603813528082811904083256440184205374679299262203769871801806112262449090924264198582086175117711378905160914038157500336642415609521632819712233502316742260056794128140621721964184270578432895980288233505982820819666624903585778994033315227481777695284368163008853176969478369058067106482808359804669884109813515865490693331952239436328792399053481098783027450017206543369906611778455436468772363184446476806914282800455107468664539280539940910875493916609573161971503316696830992946634914279878084225722069714887558063748030886299511847318712477729191007022758889348693945628951580296537215040960310776128983126358996489341024703603664505868728758905140684123812424738638542790828273382797332688550493587430316027474906312957234974261122151741715313361862241091386950068883589896234927631731647834007746088665559873338211382992877691149549218419208777160606847287467368188616750722101726110383067178785669481294878504894306308616994879870316051588410828235127415353851336589533294862949449506186851477910580469603906937266267038651290520113781085861618888694795760741358553458515176805197333443349523012039577073962377131603024288720053732099825300897761897312981788194467173116064723147624845755192873278282512718244680782421521646956781929409823892628494376024885227900362021938669648221562809360537317804086372726842669642192994681921490870170753336109479138180406328738759384826953558307739576144799727000347288018278528138950321798634521611106660883931405322694490545552786789441757920244002145078019209980446138254780585804844241640477503153605490659143007815837243012313751156228401583864427089071828481675752712384678245953433444962201009607105137060846180118754312072549133499424761711563332140893460915656155060031738421870157022610310191660388706466143889773631878094071152752817468957640158104701696524755774089164456867771715850058326994340167720215676772406812836656526412298243946513319735919970940327593850266955747023181320324371642058614103360652453693916005064495306016126782264894243739716671766123104897503188573216555498834212180284691252908610148552781527762562375045637576949773433684601560772703550962904939248708840628106794362241870474700836884267102255830240359984164595112248527263363264511401739524808619463584078375355688562231711552094722306543709260679735100056554938122457548372854571179739361575616764169289580525729752233855861138832217110736226581621884244317885748879810902665379342666421699091405653643224930133486798815488662866505234699723557473842483059042367714327879231642240387776433019260019228477831383763253612102533693581262408686669973827597736568222790721583247888864236934639616436330873013981421143030600873066616480367898409133592629340230432497492688783164360268101130957071614191283068657732353263965367739031766136131596555358499939860056515592193675997771793301974468814837110320650369319289452140265091546518430993655349333718342529843367991593941746622390038952767381333061774762957494386871697845376721949350659087571191772087547710718993796089477451265475750187119487073873678589020061737332107569330221632062843206567119209695058576117396163232621770894542621460985841023781321581772760222273813349541048100307327510779994899197796388353073444345753297591426376840544226478421606312276964696715647399904371590332390656072664411643860540483884716191210900870101913072607104411414324197679682854788552477947648180295973604943970047959604029274629920357209976195014034831538094771460105633344699882082212058728151072918297121191787642488035467231691654185225672923442918712816323259696541354858957713320833991128877591722611527337901034136208561457799239877832508355073019981845902595835598926055329967377049172245493532968330000223018151722657578752405883224908582128008974790932610076257877042865600699617621217684547899644070506624171021332748679623743022915535820078014116534806564748823061500339206898379476625503654982280532966286211793062843017049240230198571997894883689718304380518217441914766042975243725168343541121703863137941142209529588579806015293875275379903093887168357209576071522190027937929278630363726876582268124199338480816602160372215471014300737753779269906958712128928801905203160128586182549441335382078488346531163265040764242839087012101519423196165226842200371123046430067344206474771802135307012409886035339915266792387110170622186588357378121093517977560442563469499978725112544085452227481091487430725986960204027594117894258128188215995235965897918114407765335432175759525553615812800116384672031934650729680799079396371496177431211940202129757312516525376801735910155733815377200195244454362007184847566341540744232862106099761324348754884743453966598133871746609302053507027195298394327142537115576660002578442303107342955153394506048622276496668762407932435319299263925373107689213535257232108088981933916866827894828117047262450194840970097576092098372409007471797334078814182519584259809624174761013825264395513525931188504563626418830033853965243599741693132289471987830842760040136807470390409723847394583489618653979059411859931035616843686921948538205578039577388136067954990008512325944252972448666676683464140218991594456530942344065066785194841776677947047204195882204329538032631053749488312218039127967844610013972675389219511911783658766252808369005324900459741094706877291232821430463533728351995364827432583311914445901780960778288358373011185754365995898272453192531058811502630754257149394302445393187017992360816661130542625399583389794297160207033876781503301028012009599725222228080142357109476035192554443492998676781789104555906301595380976187592035893734197896235893112598390259831026719330418921510968915622506965911982832345550305908173073519550372166587028805399213857603703537710517802128012956684198414036287272562321442875430221090947272107347413497551419073704331827662617727599688882602722524713368335345281669277959132886138176634985772893690096574956228710302436259077241221909430087175569262575806570991201665962243608024287002454736203639484125595488172727247365346778364720191830399871762703751572464992228946793232269361917764161461879561395669956778306829031658969943076733350823499079062410020250613405734430069574547468217569044165154063658468046369262127421107539904218871612761778701425886482577522388918459952337629237791558574454947736129552595222657863646211837759847370034797140820699414558071908021359073226923310083175951065901912129479540860364075735875020589020870457967000705526250581142066390745921527330940682364944159089100922029668052332526619891131184201629163107689408472356436680818216865721968826835840278550078280404345371018365109695178233574303050485265373807353107418591770561039739506264035544227515610110726177937063472380499066692216197119425912044508464174638358993823994651739550900085947999013602667426149429006646711506717542217703877450767356374215478290591101261915755587023895700140511782264698994491790830179547587676016809410013583761357859135692445564776446417866711539195135769610486492249008344671548638305447791433009768048687834818467273375843689272431044740680768527862558516509208826381323362314873333671476452045087662761495038994950480956046098960432912335834885999029452640028499428087862403981181488476730121675416110662999555366819312328742570206373835202008686369131173346973174121915363324674532563087134730279217495622701468732586789173455837996435135880095935087755635624881049385299900767513551352779241242927748856588856651324730251471021057535251651181485090275047684551825209633189906852761443513821366215236889057878669943228881602837748203550601602989400911971385017987168363374413927597364401700701476370665570350433812111357641501845182141361982349515960106475271257593518530433287553778305750956742544268471221961870917856078393614451138333564910325640573389866717812397223751931643061701385953947436784339267098671245221118969084023632741149660124348309892994173803058841716661307304006758838043211155537944060549772170594282151488616567277124090338772774562909711013488518437411869565544974573684521806698291104505800429988795389902780438359628240942186055628778842880212755388480372864001944161425749990427200959520465417059810498996750451193647117277222043610261407975080968697517660023718774834801612031023468056711264476612374762785219024120256994353471622666089367521983311181351114650385489502512065577263614547360442685949807439693233129712737715734709971395229118265348515558713733662912024271430250376326950135091161295299378586468130722648600827088133353819370368259886789332123832705329762585738279009782646054559855513183668884462826513379849166783940976135376625179825824966345877195012438404035914084920973375464247448817618407002356958017741017769692507781489338667255789856458985105689196092439884156928069698335224022563457049731224526935419383700484318335719651662672157552419340193309901831930919658292096965624766768365964701959575473934551433741370876151732367720422738567427917069820454995309591887243493952409444167899884631984550485239366297207977745281439941825678945779571255242682608994086331737153889626288962940211210888442737656862452761213037101730078513571540453304150795944777614359743780374243664697324713841049212431413890357909241603640631403814983148190525172093710396402680899483257229795456404270175772290417323479607361878788991331830584306939482596131871381642346721873084513387721908697510494284376932502498165667381626061594176825250999374167288395174406693254965340310145222531618900923537648637848288134420987004809622717122640748957193900291857330746010436072919094576799461492929042798168772942648772995285843464777538690695014898413392454039414468026362540211861431703125111757764282991464453340892097696169909837265236176874560589470496817013697490952307208268288789073019001825342580534342170592871393173799314241085264739094828459641809361413847583113613057610846236683723769591349261582451622155213487924414504175684806412063652017038633012953277769902311864802006755690568229501635493199230591424639621702532974757311409422018019936803502649563695586642590676268568737211033915679383989576556519317788300024161353956243777784080174881937309502069990089089932808839743036773659552489130015663329407790713961546453408879151030065132193448667324827590794680787981942501958262232039513125201410996053126069655540424867054998678692302174698900954785072567297879476988883109348746442640071818316033165551153427615562240547447337804924621495213325852769884733626918264917433898782478927846891882805466998230368993978341374758702580571634941356843392939606819206177333179173820856243643363535986349449689078106401967407443658366707158692452118299789380407713750129085864657890577142683358276897855471768718442772612050926648610205153564284063236848180728794071712796682006072755955590404023317874944734645476062818954151213916291844429765106694796935401686601005519607768733539651161493093757096855455938151378956903925101495326562814701199832699220006639287537471313523642158926512620407288771657835840521964605410543544364216656224456504299901025658692727914275293117208279393775132610605288123537345106837293989358087124386938593438917571337630072031976081660446468393772580690923729752348670291691042636926209019960520412102407764819031601408586355842760953708655816427399534934654631450404019952853725200495780525465625115410925243799132626271360909940290226206283675213230506518393405745011209934146491843332364656937172591448932415900624202061288573292613359680872650004562828455757459659212053034131011182750130696150983551563200431078460190656549380654252522916199181995960275232770224985573882489988270746593635576858256051806896428537685077201222034792099393617926820659014216561592530673794456894907085326356819683186177226824991147261573203580764629811624401331673789278868922903259334986179702199498192573961767307583441709855922217017182571277753449150820527843090461946083521740200583867284970941102326695392144546106621500641067474020700918991195137646690448126725369153716229079138540393756007783515337416774794210038400230895185099454877903934612222086506016050035177626483161115332558770507354127924990985937347378708119425305512143697974991495186053592040383023571635272763087469321962219006426088618367610334600225547747781364101269190656968649501268837629690723396127628722304114181361006026404403003599698891994582739762411461374480405969706257676472376606554161857469052722923822827518679915698339074767114610302277660602006124687647772881909679161335401988140275799217416767879923160396356949285151363364721954061117176738737255572852294005436178517650230754469386930787349911035218253292972604455321079788771144989887091151123725060423875373484125708606406905205845212275453384800820530245045651766951857691320004281675805492481178051983264603244579282973012910531838563682120621553128866856495651261389226136706409395333457052698695969235035309422454386527867767302754040270224638448355323991475136344104405009233036127149608135549053153902100229959575658370538126196568314428605795669662215472169562087001372776853696084070483332513279311223250714863020695124539500373572334680709465648308920980153487870563349109236605755405086411152144148143463043727327104502776866195310785832333485784029716092521532609255893265560067212435946425506599677177038844539618163287961446081778927217183690888012677820743010642252463480745430047649288555340906218515365435547412547615276977266776977277705831580141218568801170502836527554321480348800444297999806215790456416195721278450892848980642649742709057912906921780729876947797511244730599140605062994689428093103421641662993561482813099887074529271604843363081840412646963792584309418544221635908457614607855856247381493142707826621518554160387020687698046174740080832434366538235455510944949843109349475994467267366535251766270677219418319197719637801570216993367508376005716345464367177672338758864340564487156696432104128259564534984138841289042068204700761559691684303899934836679354254921032811336318472259230555438305820694167562999201337317548912203723034907268106853445403599356182357631283776764063101312533521214199461186935083317658785204711236433122676512996417132521751355326186768194233879036546890800182713528358488844411176123410117991870923650718485785622102110400977699445312179502247957806950653296594038398736990724079767904082679400761872954783596349279390457697366164340535979221928587057495748169669406233427261973351813662606373598257555249650980726012366828360592834185584802695841377255897088378994291054980033111388460340193916612218669605849157148573356828614950001909759112521880039641976216355937574371801148055944229873041819680808564726571354761283162920044988031540210553059707666636274932830891688093235929008178741198573831719261672883491840242972129043496552694272640255964146352591434840067586769035038232057293413298159353304444649682944136732344215838076169483121933311981906109614295220153617029857510559432646146850545268497576480780800922133581137819774927176854507553832876887447459159373116247060109124460982942484128752022446259447763874949199784044682925736096853454984326653686284448936570411181779380644161653122360021491876876946739840751717630751684985635920148689294310594020245796962292456664488196757629434953532638217161339575779076637076456957025973880043841580589433613710655185998760075492418721171488929522173772114608115434498266547987258005667472405112200738345927157572771521858994694811794064446639943237004429114074721818022482583773601734668530074498556471542003612359339731291445859152288740871950870863221883728826282288463184371726190330577714765156414382230679184738603914768310814135827575585364359772165002827780371342286968878734979509603110889919614338666406845069742078770028050936720338723262963785603865321643234881555755701846908907464787912243637555666867806761054495501726079114293083128576125448194444947324481909379536900820638463167822506480953181040657025432760438570350592281891987806586541218429921727372095510324225107971807783304260908679427342895573555925272380551144043800123904168771644518022649168164192740110645162243110170005669112173318942340054795968466980429801736257040673328212996215368488140410219446342464622074557564396045298531307140908460849965376780379320189914086581466217531933766597011433060862500982956691763884605676297293146491149370462446935198403953444913514119366793330193661766365255514917498230798707228086085962611266050428929696653565251668888557211227680277274370891738963977225756489053340103885593112567999151658902501648696142720700591605616615970245198905183296927893555030393468121976158218398048396056252309146263844738629603984892438618729850777592879272206855480721049781765328621018747676689724884113956034948037672703631692100735083407386526168450748249644859742813493648037242611670426687083192504099761531907685577032742178501000644198412420739640013960360158381056592841368457411910273642027416372348821452410134771652960312840865841978795111651152982781462037913985500639996032659124852530849369031313010079997719136223086601109992914287124938854161203802041134018888721969347790449752745428807280350930582875442075513481666092787935356652125562013998824962847872621443236285367650259145046837763528258765213915648097214192967554938437558260025316853635673137926247587804944594418342917275698837622626184636545274349766241113845130548144983631178978448973207671950878415861887969295581973325069995140260151167552975057543781024223895792578656212843273120220071673057406928686936393018676595825132649914595026091706934751940897535746401683081179884645247361895605647942635807056256328118926966302647953595109712765913623318086692153578860781275991053717140220450618607537486630635059148391646765672320571451688617079098469593223672494673758309960704258922048155079913275208858378111768521426933478692189524062265792104362034885292626798401395321645879115157905046057971083898337186403802441751134722647254701079479399695355466961972676325522991465493349966323418595145036098034409221220671256769872342794070885707047429317332918852389672197135392449242617864118863779096281448691786946817759171715066911148002075943201206196963779510322708902956608556222545260261046073613136886900928172106819861855378098201847115416363032626569928342415502360097804641710852553761272890533504550613568414377585442967797701466029438768722511536380119175815402812081825560648541078793359892106442724489861896162941341800129513068363860929410008313667337215300835269623573717533073865333820484219030818644918409372394403340524490955455801640646076158101030176748847501766190869294609876920169120218168829104087070956095147041692114702741339005225334083481287035303102391969997859741390859360543359969707560446013424245368249609877258131102473279856207212657249900346829388687230489556225320446360263985422525841646432427161141981780248259556354490721922658386366266375083594431487763515614571074552801615967704844271419443518327569840755267792641126176525061596523545718795667317091331935876162825592078308018520689015150471334038610031005591481785211038475454293338918844412051794396997019411269511952656491959418997541839323464742429070271887522353439367363366320030723274703740712398256202466265197409019976245205619855762576000870817308328834438183107005451449354588542267857855191537229237955549433341017442016960009069641561273229777022121795186837635908225512881647002199234886404395915301846400471432118636062252701154112228380277853891109849020134274101412155976996543887719748537643115822983853312307175113296190455900793806427669581901484262799122179294798734890186847167650382732855205908298452980625925035212845192592798659350613296194679625237397256558415785374456755899803240549218696288849033256085145534439166022625777551291620077279685262938793753045418108072928589198971538179734349618723292761474785019261145041327487324297058340847111233374627461727462658241532427105932250625530231473875925172478732288149145591560503633457542423377916037495250249302235148196138116256391141561032684495807250827343176594405409826976526934457986347970974312449827193311386387315963636121862349726140955607992062831699942007205481152535339394607685001990988655386143349578165008996164907967814290114838764568217491407562376761845377514403147541120676016072646055685925779932207033733339891636950434669069482843662998003741452762771654762382554617088318981086880684785370553648046935095881802536052974079353867651119507937328208314626896007107517552061443378411454995013643244632819334638905093654571450690086448344018042836339051357815727397333453728426337217406577577107983051755572103679597690188995849413019599957301790124019390868135658553966194137179448763207986880037160730322054742357226689680188212342439188598416897227765219403249322731479366923400484897605903795809469604175427961378255378122394764614783292697654516229028170110043784603875654415173943396004891531881757665050095169740241564477129365661425394936888423051740012992055685428985389794266995677702708914651373689220610441548166215680421983847673087178759027920917590069527345668202651337311151800018143412096260165862982107666352336177400783778342370915264406305407180784335806107296110555002041513169637304684921335683726540030750982908936461204789111475303704989395283345782408281738644132271000296831194020332345642082647327623383029463937899837583655455991934086623509096796113400486702712317652666371077872511186035403755448741869351973365662177235922939677646325156202348757011379571209623772343137021203100496515211197601317641940820343734851285260291333491512508311980285017785571072537314913921570910513096505988599993156086365547740355189816673353588004821466509974143376118277772335191074121757284159258087259131507460602563490377726337391446137703802131834744730111303267029691733504770163210661622783002726928336558401179141944780874825336071440329625228577500980859960904093631263562132816207145340610422411208301000858726425211226248014264751942618432585338675387405474349107271004975428115946601713612259044015899160022982780179603519408004651353475269877760952783998436808690898919783969353217998013913544255271791022539701081063214304851137829149851138196914304349750018998068164441212327332830719282436240673319655469267785119315277511344646890550424811336143498460484905125834568326644152848971397237604032821266025351669391408204994732048602162775979177123475109750240307893575993771509502175169355582707253391189233407022383207758580213717477837877839101523413209848942345961369234049799827930414446316270721479611745697571968123929191374098292580556195520743424329598289898052923336641541925636738068949420147124134052507220406179435525255522500874879008656831454283516775054229480327478304405643858159195266675828292970522612762871104013480178722480178968405240792436058274246744307672164527031345135416764966890127478680101029513386269864974821211862904033769156857624069929637249309720162870720018983542369036414927023696193854737248032985504511208919287982987446786412915941753167560253343531062674525450711418148323988060729714023472552071349079839898235526872395090936566787899238371257897624875599044322889538837731734894112275707141095979004791930104674075041143538178246463079598955563899188477378134134707024674736211204898622699188851745625173251934135203811586335012391305444191007362844756751416105041097350585276204448919097890198431548528053398577784431393388399431044446566924455088594631408175122033139068159659251054685801313383815217641821043342978882611963044311138879625874609022613090084997543039577124323061690626291940392143974027089477766370248815549932245882597902063125743691094639325280624164247686849545532493801763937161563684785982371590238542126584061536722860713170267474013114526106376538339031592194346981760535838031061288785205154693363924108846763200956708971836749057816308515813816196688222204757043759061433804072585386208356517699842677452319582418268369827016023741493836349662935157685406139734274647089968561817016055110488097155485911861718966802597354170542398513556001872033507906094642127114399319604652742405088222535977348151913543857125325854049394601086579379805862014336607882521971780902581737087091646045272797715350991034073642502038638671822052287969445838765294795104866071739022932745542678566977686593992341683412227466301506215532050265534146099524935605085492175654913483095890653617569381763747364418337897422970070354520666317092960759198962773242309025239744386101426309868773391388251868431650102796491149773758288891345034114886594867021549210108432808078342808941729800898329753694064496990312539986391958160146899522088066228540841486427478628197554662927881462160717138188018084057208471586890683691939338186427845453795671927239797236465166759201105799566396259853551276355876814021340982901629687342985079247184605687482833138125916196247615690287590107273310329914062386460833337863825792630239159000355760903247728133888733917809696660146961503175422675112599331552967421333630022296490648093458200818106180210022766458040027821333675857301901137175467276305904435313131903609248909724642792845554991349000518029570708291905255678188991389962513866231938005361134622429461024895407240485712325662888893172211643294781619055486805494344103409068071608802822795968695013364381426825217047287086301013730115523686141690837567574763723976318575703810944339056456446852418302814810799837691851212720193504404180460472162693944578837709010597469321972055811407877598977207200968938224930323683051586265728111463799698313751793762321511125234973430524062210524423435373290565516340666950616589287821870775679417608071297378133518711793165003315552382248773065344417945341539520242444970341012087407218810938826816751204229940494817944947273289477011157413944122845552182842492224065875268917227278060711675404697300803703961878779669488255561467438439257011582954666135867867189766129731126720007297155361302750355616781776544228744211472988161480270524380681765357327557860250584708401320883793281600876908130049249147368251703538221961903901499952349538710599735114347829233949918793660869230137559636853237380670359114424326856151210940425958263930167801712866923928323105765885171402021119695706479981403150563304514156441462316376380990440281625691757648914256971416359843931743327023781233693804301289262637538266779503416933432360750024817574180875038847509493945489620974048544263563716499594992098088429479036366629752600324385635294584472894454716620929749549661687741412088213047702281611645604400723635158114972973921896673738264720472264222124201656015028497130633279581430251601369482556701478093579088965713492615816134690180696508955631012121849180584792272069187169631633004485802010286065785859126997463766174146393415956953955420331462802651895116793807457331575984608617370268786760294367778050024467339133243166988035407323238828184750105164133118953703648842269027047805274249060349208295475505400345716018407257453693814553117535421072655783561549987444748042732345788006187314934156604635297977945507535930479568720931672453654720838168585560604380197703076424608348987610134570939487700294617579206195254925575710903852517148852526567104534981341980339064152987634369542025608027761442191431892139390883454313176968510184010384447234894886952098194353190650655535461733581404554483788475252625394966586999205841765278012534103389646981864243003414679138061902805960785488801078970551694621522877309010446746249797999262712095168477956848258334140226647721084336243759374161053673404195473896419789542533503630186140095153476696147625565187382329246854735693580289601153679178730355315937836308224861517777054157757656175935851201669294311113886358215966761883032610416465171484697938542262168716140012237821377977413126897726671299202592201740877007695628347393220108815935628628192856357189338495885060385315817976067947984087836097596014973342057270460352179060564760328556927627349518220323614411258418242624771201203577638889597431823282787131460805353357449429762179678903456816988955351850447832561638070947695169908624710001974880920500952194363237871976487033922381154036347548862684595615975519376541011501406700122692747439388858994385973024541480106123590803627458528849356325158538438324249325266608758890831870070910023737710657698505643392885433765834259675065371500533351448990829388773735205145933304962653141514138612443793588507094468804548697535817021290849078734780681436632332281941582734567135644317153796781805819585246484008403290998194378171817730231700398973305049538735611626102399943325978012689343260558471027876490107092344388463401173555686590358524491937018104162620850429925869743581709813389404593447193749387762423240985283276226660494238512970945324558625210360082928664972417491914198896612955807677097959479530601311915901177394310420904907942444886851308684449370590902600612064942574471035354765785924270813041061854621988183009063458818703875585627491158737542106466795134648758677154383801852134828191581246259933516019893559516796893285220582479942103451271587716334522299541883968044883552975336128683722593539007920166694133909116875880398882886921600237325736158820716351627133281051818760210485218067552664867390890090719513805862673512431221569163790227732870541084203784152568328871804698795251307326634027851905941733892035854039567703561132935448258562828761061069822972142096199350933131217118789107876687204454887608941017479864713788246215395593333327556200943958043453791978228059039595992743691379377866494096404877784174833643268402628293240626008190808180439091455635193685606304508914228964521998779884934747772913279726602765840166789013649050874114212686196986204412696528298108704547986155954533802120115564697997678573892018624359932677768945406050821883822790983
```

## C#

Translation of: Java

`using System;using System.Numerics; namespace PiCalc {    internal class Program {        private readonly BigInteger FOUR = new BigInteger(4);        private readonly BigInteger SEVEN = new BigInteger(7);        private readonly BigInteger TEN = new BigInteger(10);        private readonly BigInteger THREE = new BigInteger(3);        private readonly BigInteger TWO = new BigInteger(2);         private BigInteger k = BigInteger.One;        private BigInteger l = new BigInteger(3);        private BigInteger n = new BigInteger(3);        private BigInteger q = BigInteger.One;        private BigInteger r = BigInteger.Zero;        private BigInteger t = BigInteger.One;         public void CalcPiDigits() {            BigInteger nn, nr;            bool first = true;            while (true) {                if (BigInteger.Subtract(BigInteger.Add(BigInteger.Multiply(FOUR, q), r), t).CompareTo(BigInteger.Multiply(n, t)) == -1) {                    Console.Write(n);                    if (first) {                        Console.Write(".");                        first = false;                    }                    nr = BigInteger.Multiply(TEN, BigInteger.Subtract(r, BigInteger.Multiply(n, t)));                    n = BigInteger.Subtract(BigInteger.Divide(BigInteger.Multiply(TEN, BigInteger.Add(BigInteger.Multiply(THREE, q), r)), t), BigInteger.Multiply(TEN, n));                    q = BigInteger.Multiply(q, TEN);                    r = nr;                } else {                    nr = BigInteger.Multiply(BigInteger.Add(BigInteger.Multiply(TWO, q), r), l);                    nn = BigInteger.Divide(BigInteger.Add(BigInteger.Add(BigInteger.Multiply(q, (BigInteger.Multiply(SEVEN, k))), TWO), BigInteger.Multiply(r, l)), BigInteger.Multiply(t, l));                    q = BigInteger.Multiply(q, k);                    t = BigInteger.Multiply(t, l);                    l = BigInteger.Add(l, TWO);                    k = BigInteger.Add(k, BigInteger.One);                    n = nn;                    r = nr;                }            }        }         private static void Main(string[] args) {            new Program().CalcPiDigits();        }    }}`

## D

This modified Spigot algorithm does not continue infinitely, because its required memory grow as the number of digits need to print.

`import std.stdio, std.conv, std.string; struct PiDigits {    immutable uint nDigits;     int opApply(int delegate(ref string /*chunk of pi digit*/) dg){        // Maximum width for correct output, for type ulong.        enum size_t width = 9;         enum ulong scale = 10UL ^^ width;        enum ulong initDigit = 2UL * 10UL ^^ (width - 1);        enum string formatString = "%0" ~ text(width) ~ "d";         immutable size_t len = 10 * nDigits / 3;        auto arr = new ulong[len];        arr[] = initDigit;        ulong carry;         foreach (i; 0 .. nDigits / width) {            ulong sum;            foreach_reverse (j; 0 .. len) {                auto quo = sum * (j + 1) + scale * arr[j];                arr[j] = quo % (j*2 + 1);                sum = quo / (j*2 + 1);            }            auto yield = format(formatString, carry + sum/scale);            if (dg(yield))                break;            carry = sum % scale;        }        return 0;    }} void main() {    foreach (d; PiDigits(100))        writeln(d);}`

Output:

```314159265
358979323
846264338
327950288
419716939
937510582
097494459
230781640
628620899
862803482
534211706```

### Alternative version

`import std.stdio, std.bigint; void main() {    int ndigits = 0;    auto q = BigInt(1);    auto r = BigInt(0);    auto t = q;    auto k = q;    auto n = BigInt(3);    auto l = n;     bool first = true;    while (ndigits < 1_000) {        if (4 * q + r - t < n * t) {            write(n); ndigits++;            if (ndigits % 70 == 0) writeln();            if (first) { first = false; write('.'); }            auto nr = 10 * (r - n * t);            n = ((10 * (3 * q + r)) / t) - 10 * n;            q *= 10;            r = nr;        } else {            auto nr = (2    * q + r) * l;            auto nn = (q * (7 * k + 2) + r * l) / (t * l);            q *= k;            t *= l;            l += 2;            k++;            n = nn;            r = nr;        }    }}`

Output:

```3.141592653589793238462643383279502884197169399375105820974944592307816
4062862089986280348253421170679821480865132823066470938446095505822317
2535940812848111745028410270193852110555964462294895493038196442881097
5665933446128475648233786783165271201909145648566923460348610454326648
2133936072602491412737245870066063155881748815209209628292540917153643
6789259036001133053054882046652138414695194151160943305727036575959195
3092186117381932611793105118548074462379962749567351885752724891227938
1830119491298336733624406566430860213949463952247371907021798609437027
7053921717629317675238467481846766940513200056812714526356082778577134
2757789609173637178721468440901224953430146549585371050792279689258923
5420199561121290219608640344181598136297747713099605187072113499999983
7297804995105973173281609631859502445945534690830264252230825334468503
5261931188171010003137838752886587533208381420617177669147303598253490
4287554687311595628638823537875937519577818577805321712268066130019278
76611195909216420198```

## Erlang

`% Implemented by Arjun Sunel-module(pi_calculation).-export([main/0]). main() ->	pi(1,0,1,1,3,3,0). pi(Q,R,T,K,N,L,C)   -> 	if C=:=50 ->		io:format("\n"),		pi(Q,R,T,K,N,L,0)  ; 	true -> 		if 			(4*Q + R-T) < (N*T) -> 			io:format("~p",[N]),	 		P = 10*(R-N*T),	 		pi(Q*10 , P, T , K , ((10*(3*Q+R)) div T)-10*N , L,C+1); 		true ->			P = (2*Q+R)*L,			M = (Q*(7*K)+2+(R*L)) div (T*L),			H  = L+2,			J =K+ 1,			pi(Q*K, P , T*L ,J,M,H,C)	 	end 	end.	 `
Output:
```31415926535897932384626433832795028841971693993751
05820974944592307816406286208998628034825342117067
98214808651328230664709384460955058223172535940812
84811174502841027019385211055596446229489549303819
64428810975665933446128475648233786783165271201909
14564856692346034861045432664821339360726024914127
37245870066063155881748815209209628292540917153643
67892590360011330530548820466521384146951941511609
43305727036575959195309218611738193261179310511854
80744623799627495673518857527248912279381830119491
29833673362440656643086021394946395224737190702179
86094370277053921717629317675238467481846766940513
20005681271452635608277857713427577896091736371787
21468440901224953430146549585371050792279689258923
54201995611212902196086403441815981362977477130996
05187072113499999983729780499510597317328160963185
95024459455346908302642522308253344685035261931188
17101000313783875288658753320838142061717766914730
35982534904287554687311595628638823537875937519577
81857780532171226806613001927876611195909216420198
93809525720106548586327886593615338182796823030195
20353018529689957736225994138912497217752834791315
15574857242454150695950829533116861727855889075098
38175463746493931925506040092770167113900984882401
28583616035637076601047101819429555961989467678374
4944825537977472684710404753464620```

## F#

`let rec g q r t k n l = seq {    if 4I*q+r-t < n*t    then        yield n        yield! (g (10I*q) (10I*(r-n*t)) t k ((10I*(3I*q+r))/t - 10I*n) l)    else        yield! (g (q*k) ((2I*q+r)*l) (t*l) (k+1I) ((q*(7I*k+2I)+r*l)/(t*l)) (l+2I))} let π = (g 1I 0I 1I 1I 3I 3I) Seq.take 1 π |> Seq.iter (printf "%A.")// 6 digits beginning at position 762 of π are '9'Seq.take 767 (Seq.skip 1 π) |> Seq.iter (printf "%A")`
Output:
```3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679821480865132823066
470938446095505822317253594081284811174502841027019385211055596446229489549303819644288109756659334461284756482337867831
652712019091456485669234603486104543266482133936072602491412737245870066063155881748815209209628292540917153643678925903
600113305305488204665213841469519415116094330572703657595919530921861173819326117931051185480744623799627495673518857527
248912279381830119491298336733624406566430860213949463952247371907021798609437027705392171762931767523846748184676694051
320005681271452635608277857713427577896091736371787214684409012249534301465495853710507922796892589235420199561121290219
6086403441815981362977477130996051870721134999999```

## Go

Code below is a simplistic translation of Haskell code in Unbounded Spigot Algorithms for the Digits of Pi. This is the algorithm specified for the pidigits benchmark of the Computer Language Benchmarks Game. (The standard Go distribution includes source submitted to the benchmark site, and that code runs stunning faster than the code below.)

`package main import (    "fmt"    "math/big") type lft struct {    q,r,s,t big.Int} func (t *lft) extr(x *big.Int) *big.Rat {    var n, d big.Int    var r big.Rat    return r.SetFrac(        n.Add(n.Mul(&t.q, x), &t.r),        d.Add(d.Mul(&t.s, x), &t.t))} var three = big.NewInt(3)var four = big.NewInt(4) func (t *lft) next() *big.Int {    r := t.extr(three)    var f big.Int    return f.Div(r.Num(), r.Denom())} func (t *lft) safe(n *big.Int) bool {    r := t.extr(four)    var f big.Int    if n.Cmp(f.Div(r.Num(), r.Denom())) == 0 {        return true    }    return false} func (t *lft) comp(u *lft) *lft {    var r lft    var a, b big.Int    r.q.Add(a.Mul(&t.q, &u.q), b.Mul(&t.r, &u.s))    r.r.Add(a.Mul(&t.q, &u.r), b.Mul(&t.r, &u.t))    r.s.Add(a.Mul(&t.s, &u.q), b.Mul(&t.t, &u.s))    r.t.Add(a.Mul(&t.s, &u.r), b.Mul(&t.t, &u.t))    return &r} func (t *lft) prod(n *big.Int) *lft {    var r lft    r.q.SetInt64(10)    r.r.Mul(r.r.SetInt64(-10), n)    r.t.SetInt64(1)    return r.comp(t)} func main() {    // init z to unit    z := new(lft)    z.q.SetInt64(1)    z.t.SetInt64(1)     // lfts generator    var k int64    lfts := func() *lft {        k++        r := new(lft)        r.q.SetInt64(k)        r.r.SetInt64(4*k+2)        r.t.SetInt64(2*k+1)        return r    }     // stream    for {        y := z.next()        if z.safe(y) {            fmt.Print(y)            z = z.prod(y)        } else {            z = z.comp(lfts())        }    }}`

## Groovy

Translation of: Java

Solution:

`BigInteger q = 1, r = 0, t = 1, k = 1, n = 3, l = 3String nnboolean first = true while (true) {    (nn, first, q, r, t, k, n, l) = (4*q + r - t < n*t) \        ? ["\${n}\${first?'.':''}", false, 10*q, 10*(r - n*t), t  , k    , 10*(3*q + r)/t - 10*n    , l    ] \        : [''                   , first, q*k , (2*q + r)*l , t*l, k + 1, (q*(7*k + 2) + r*l)/(t*l), l + 2]    print nn}`

Output (thru first 1000 iterations):

`3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679821480865132823066470938446095505822317253594081284811174502841027019385211055596446229489549303819644288109756659334461284756482337`

The code from [2]:

`pi_ = g(1,0,1,1,3,3) where  g (q,r,t,k,n,l) =    if 4*q+r-t < n*t    then n : g (10*q, 10*(r-n*t), t, k, div (10*(3*q+r)) t - 10*n, l)    else g (q*k, (2*q+r)*l, t*l, k+1, div (q*(7*k+2)+r*l) (t*l), l+2)`

## Icon and Unicon

Translation of: PicoLisp
based on Jeremy Gibbons' Haskell solution.
`procedure pi (q, r, t, k, n, l)  first := "yes"  repeat { # infinite loop    if (4*q+r-t < n*t) then {      suspend n      if (\first) := &null then suspend "."      # compute and update variables for next cycle      nr := 10*(r-n*t)      n := ((10*(3*q+r)) / t) - 10*n      q *:= 10      r := nr    } else {      # compute and update variables for next cycle      nr := (2*q+r)*l      nn := (q*(7*k+2)+r*l) / (t*l)      q *:= k      t *:= l      l +:= 2      k +:= 1      n := nn      r := nr    }  }end procedure main ()  every (writes (pi (1,0,1,1,3,3)))end`

## J

`pi=:3 :0  smoutput"0'3.1'  n=.0 while.n=.n+1 do.    smoutput-/1 10*<.@o.10x^1 0+n  end.)`

Example use:

`   pi''3.141592653...`

## Java

Translation of: Icon
`import java.math.BigInteger ; public class Pi {  final BigInteger TWO = BigInteger.valueOf(2) ;  final BigInteger THREE = BigInteger.valueOf(3) ;  final BigInteger FOUR = BigInteger.valueOf(4) ;  final BigInteger SEVEN = BigInteger.valueOf(7) ;   BigInteger q = BigInteger.ONE ;  BigInteger r = BigInteger.ZERO ;  BigInteger t = BigInteger.ONE ;  BigInteger k = BigInteger.ONE ;  BigInteger n = BigInteger.valueOf(3) ;  BigInteger l = BigInteger.valueOf(3) ;   public void calcPiDigits(){    BigInteger nn, nr ;    boolean first = true ;    while(true){        if(FOUR.multiply(q).add(r).subtract(t).compareTo(n.multiply(t)) == -1){          System.out.print(n) ;          if(first){System.out.print(".") ; first = false ;}          nr = BigInteger.TEN.multiply(r.subtract(n.multiply(t))) ;          n = BigInteger.TEN.multiply(THREE.multiply(q).add(r)).divide(t).subtract(BigInteger.TEN.multiply(n)) ;          q = q.multiply(BigInteger.TEN) ;          r = nr ;          System.out.flush() ;        }else{          nr = TWO.multiply(q).add(r).multiply(l) ;          nn = q.multiply((SEVEN.multiply(k))).add(TWO).add(r.multiply(l)).divide(t.multiply(l)) ;          q = q.multiply(k) ;          t = t.multiply(l) ;          l = l.add(TWO) ;          k = k.add(BigInteger.ONE) ;          n = nn ;          r = nr ;        }    }  }   public static void main(String[] args) {    Pi p = new Pi() ;    p.calcPiDigits() ;  }}`

Output :

`3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679821480 ...`

## Julia

Julia comes with built-in support for computing π in arbitrary precision (using the GNU MPFR library). This implementation computes π at precisions that are repeatedly doubled as more digits are needed, printing one digit at a time and never terminating (until it runs out of memory) as specified:

`prec = get_bigfloat_precision()spi = ""digit = 1while true  if digit > length(spi) - 6    prec *= 2    set_bigfloat_precision(prec)    spi = string(big(π))  end  print(spi[digit])  digit += 1end`

Output:

`3.141592653589793238462643383279502884195e69399375105820974944592307816406286198e9862803482534211706798214808651328230664709384460955058223172535940812848115e450284102701938521105559644622948954930381964428810975665933446128475648233786783165271201909145648566923460348610454326648213393607260249141273724586997e0631558817488152092096282925409171536436789259036001133053054882046652138414695194151160943305727036575959195309218611738193261179310511854807446237996274956735188575272489122793818301194912983367336244065664308602139494639522473719070217986094370277053921717629317675238467481846766940513200056812714526357e8277857713427577896091736371787214684409012249534301465495853710507922796892589235420199561121290219608640344181598136297747713099605187072113499999983729780499510597317328160963185950244594553469083026425223082533446850352619311881710100031378387528865875332083814206171776691473035982534904287554687311595628638823537875937519577818577805321712268066130019278766111959092164201...`

## Lasso

`#!/usr/bin/lasso9 define generatePi => {  yield currentCapture   local(r = array(), i, k, b, d, c = 0, x)  with i in generateSeries(1, 2800)  do #r->insert(2000)  with k in generateSeries(2800, 1, -14)  do {    #d = 0    #i = #k    while(true) => {      #d += #r->get(#i) * 10000      #b = 2 * #i - 1      #r->get(#i) = #d % #b      #d /= #b      #i--      !#i ? loop_abort      #d *= #i    }    #x = (#c + #d / 10000)    yield (#k == 2800 ? ((#x * 0.001)->asstring(-precision = 3)) | #x->asstring(-padding=4, -padChar='0'))    #c = #d % 10000  }} local(pi_digits) = generatePiloop(200) => {    stdout(#pi_digits())}`

Output (first 100 places):

```3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342117067
```

## Liberty BASIC

Pretty slow if you run for over 100 digits...

`    ndigits = 0     q       = 1    r       = 0    t       = q    k       = q    n       = 3    L       = n    first = 666  '   ANY non-zero =='true' in LB.     while ndigits <100        if ( 4 *q +r -t) <( n *t) then            print n;            ndigits =ndigits +1            if not( ndigits mod 40) then print: print "  ";            if first =666 then first = 0: print ".";            nr =10 *( r -n *t)            n  =int( ( (10 *( 3 *q +r)) /t) -10 *n)            q  =q *10            r  =nr        else            nr =( 2 *q +r) *L            nn =(q *( 7 *k +2) +r *L) /( t *L)            q  =q *k            t  =t *L            L  =L +2            k  =k +1            n  =int( nn)            r  =nr        end if        scanwend end`
```3.141592653589793238462643383279502884197
1693993751058209749445923078164062862089
98628034825342117067
```

## Mathematica

User can interrupt computation using "Alt+." or "Cmd+." on a Mac.

`N[Pi, 1000000!]`

## MATLAB / Octave

Matlab / Octave use double precesion numbers per default, and pi is a builtin constant value. Arbitrary precision is only implemented in some additional toolboxes (e.g. symbolic toolbox).

`pi`
```>> pi
ans =  3.1416
> printf('%.60f\n',pi)
3.141592653589793115997963468544185161590576171875000000000000>> format long
```
```Unfortunately this is not the correct value!
3.14159265358979323846264338327950288419716939937510582
=================??????????????????????????????????????```

## NetRexx

Translation of: Java
`/* NetRexx */options replace format comments java crossref symbols binaryimport java.math.BigInteger runSample(arg)return -- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~method runSample(arg) private static  parse arg places .  if places = '' then places = -1   TWO   = BigInteger.valueOf(2)  THREE = BigInteger.valueOf(3)  FOUR  = BigInteger.valueOf(4)  SEVEN = BigInteger.valueOf(7)   q_ = BigInteger.ONE  r_ = BigInteger.ZERO  t_ = BigInteger.ONE  k_ = BigInteger.ONE  n_ = BigInteger.valueOf(3)  l_ = BigInteger.valueOf(3)   nn = BigInteger  nr = BigInteger   first = isTrue()  digitCt = 0  loop forever    if FOUR.multiply(q_).add(r_).subtract(t_).compareTo(n_.multiply(t_)) == -1 then do      digitCt = digitCt + 1      if places > 0 & digitCt - 1 > places then leave      say n_'\-'      if first then do        say '.\-'        first = isFalse()        end      nr = BigInteger.TEN.multiply(r_.subtract(n_.multiply(t_)))      n_ = BigInteger.TEN.multiply(THREE.multiply(q_).add(r_)).divide(t_).subtract(BigInteger.TEN.multiply(n_))      q_ = q_.multiply(BigInteger.TEN)      r_ = nr      end    else do      nr = TWO.multiply(q_).add(r_).multiply(l_)      nn = q_.multiply((SEVEN.multiply(k_))).add(TWO).add(r_.multiply(l_)).divide(t_.multiply(l_))      q_ = q_.multiply(k_)      t_ = t_.multiply(l_)      l_ = l_.add(TWO)      k_ = k_.add(BigInteger.ONE)      n_ = nn      r_ = nr      end    end  say   return method isTrue() private static returns boolean  return (1 == 1)method isFalse() private static returns boolean  return \isTrue() `
Output:
```3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679...
```

## OCaml

The Constructive Real library Creal contains an infinite-precision Pi, so we can just print out its digits.

`open Creal;; let block = 100 inlet segment n =   let s = to_string pi (n*block) in   String.sub s ((n-1)*block) block inlet counter = ref 1 inwhile true do   print_string (segment !counter);   flush stdout;   incr counterdone`

However that is cheating if you want to see an algorithm to generate Pi. Since the Spigot algorithm is already used in the pidigits program, this implements Machin's formula.

`open Num (* series for: c*atan(1/k) *)class atan_sum c k = object   val kk = k*/k   val mutable n = 0   val mutable kpow = k   val mutable pterm = c*/k   val mutable psum = Int 0   val mutable sum = c*/k   method next =      n <- n+1; kpow <- kpow*/kk;      let t = c*/kpow//(Int (2*n+1)) in      pterm <- if n mod 2 = 0 then t else minus_num t;      psum <- sum;      sum <- sum +/ pterm   method error = abs_num pterm   method bounds = if pterm </ Int 0 then (sum, psum) else (psum, sum)end;; let inv i = (Int 1)//(Int i) inlet t1 = new atan_sum (Int 16) (inv 5) inlet t2 = new atan_sum (Int (-4)) (inv 239) inlet base = Int 10 inlet npr = ref 0 inlet shift = ref (Int 1) inlet d_acc = inv 10000 inlet acc = ref d_acc inlet shown = ref (Int 0) inwhile true do   while t1#error >/ !acc do t1#next done;   while t2#error >/ !acc do t2#next done;   let (lo1, hi1), (lo2, hi2) = t1#bounds, t2#bounds in   let digit x = int_of_num (floor_num ((x -/ !shown) */ !shift)) in   let d, d' = digit (lo1+/lo2), digit (hi1+/hi2) in   if d = d' then (      print_int d;      if !npr = 0 then print_char '.';      flush stdout;      shown := !shown +/ ((Int d) // !shift);      incr npr; shift := !shift */ base;   ) else (acc := !acc */ d_acc);done`

## PARI/GP

Uses the built-in Brent-Salamin arithmetic-geometric mean iteration.

`pi()={  my(x=Pi,n=0,t);  print1("3.");  while(1,    if(n>=default(realprecision),      default(realprecision,default(realprecision)*2);      x=Pi    );    print1(floor(x*10^n++)%10)  )};`

## Pascal

Works with: Free_Pascal

`Program Pi_Spigot; const  n   = 1000;  len = 10*n div 3; var  i, j, k, q, x, nines, predigit: integer;  a: array[1..len] of longint; begin  for j := 1 to len do    a[j] := 2;                 {Start with 2s}  nines := 0;  predigit := 0;               {First predigit is a 0}  for j := 1 to n do  begin    q := 0;    for i := len downto 1 do   {Work backwards}    begin      x    := 10*a[i] + q*i;      a[i] := x mod (2*i - 1);      q    := x div (2*i - 1);    end;    a[1] := q mod 10;    q := q div 10;    if q = 9 then      nines := nines + 1    else      if q = 10 then      begin	write(predigit+1);	for k := 1 to nines do	  write(0);            {zeros}	predigit := 0;	nines := 0      end      else      begin	write(predigit);	predigit := q;	if nines <> 0 then	begin	  for k := 1 to nines do	    write(9);	  nines := 0	end      end  end;  writeln(predigit);end. `

Output:

```% ./Pi_Spigot
0314159265358979323846264338327950288419716939937510582097494459230781640628620899862803482534211706798214808651328230664709384460955058223172535940812848111745028410270193852110555964462294895493038196442881097566593344612847564823378678316527120190914564856692345909920711885680651674519425285434096427182587759486723722781805263647624000125396676958803786501460828202281029373153209312571960818250880554547473856719984185863746093965326651520597323020047032736774801454941806997686761324327197543884752285691446935454123565860783675210974816763774404244435759134410295498726734853215534522607487460726127229475668144011717114616426232946428024519416553103668226495999762474794964971942580962672394353639091253676024666416611752768663496859511953379074492301907334533332168653316848429072409790153107727405217592705578811026822246918375946146833893295768948223454910618813165693638675020776147309271039650546608291414446931319129743860775232869818000001373465107828774083538328579350606183962012466```

## Perl

Translation of: Perl 6
`use bigint;sub stream {     my (\$next, \$safe, \$prod, \$cons, \$z, \$x) = @_;    \$x = \$x->();    sub {        while (1) {            my \$y = \$next->(\$z);            if (\$safe->(\$z, \$y)) {                \$z = \$prod->(\$z, \$y);                return \$y;            } else {                \$z = \$cons->(\$z, \$x->());            }        }    }} sub extr {    use integer;    my (\$q, \$r, \$s, \$t) = @{shift()};    my \$x = shift;    (\$q * \$x + \$r) / (\$s * \$x + \$t);} sub comp {    my (\$q, \$r, \$s, \$t) = @{shift()};    my (\$u, \$v, \$w, \$x) = @{shift()};    [\$q * \$u + \$r * \$w,     \$q * \$v + \$r * \$x,     \$s * \$u + \$t * \$w,     \$s * \$v + \$t * \$x];} my \$pi_stream = stream    sub { extr shift, 3 },    sub { my (\$z, \$n) = @_; \$n == extr \$z, 4 },    sub { my (\$z, \$n) = @_; comp([10, -10*\$n, 0, 1], \$z) },    \&comp,    [1, 0, 0, 1],    sub { my \$n = 0; sub { \$n++; [\$n, 4 * \$n + 2, 0, 2 * \$n + 1] } },;\$|++;print \$pi_stream->(), '.';print \$pi_stream->() while 1;`

Here is an original Perl 5 code, using Machin's formula. Not the fastest program in the world.

`use Math::BigInt;use bigint; # Pi/4 = 4 arctan 1/5 - arctan 1/239# expanding it with Taylor series with what's probably the dumbest method my (\$ds, \$ns) = (1, 0);my (\$n5, \$d5) = (16 * (25 * 3 - 1), 3 * 5**3);my (\$n2, \$d2) = (4 * (239 * 239 * 3 - 1), 3 * 239**3); sub next_term {	my (\$coef, \$p) = @_[1, 2];	\$_[0] /= (\$p - 4) * (\$p - 2);	\$_[0] *= \$p * (\$p + 2) * \$coef**4;} my \$p2 = 5;my \$pow = 1; \$| = 1;for (my \$x = 5; ; \$x += 4) {	(\$ns, \$ds) = (\$ns * \$d5 + \$n5 * \$pow * \$ds, \$ds * \$d5); 	next_term(\$d5, 5, \$x);	\$n5 = 16 * (5 * 5 * (\$x + 2) - \$x); 	while (\$d5 > \$d2) {		(\$ns, \$ds) = (\$ns * \$d2 - \$n2 * \$pow * \$ds, \$ds * \$d2);		\$n2 = 4 * (239 * 239 * (\$p2 + 2) - \$p2);		next_term(\$d2, 239, \$p2);		\$p2 += 4;	} 	my \$ppow = 1;	while (\$pow * \$n5 * 5**4 < \$d5 && \$pow * \$n2 * \$n2 * 239**4 < \$d2) {		\$pow *= 10;		\$ppow *= 10;	} 	if (\$ppow > 1) {		\$ns *= \$ppow;	#FIX?	my \$out = \$ns->bdiv(\$ds);   # bugged?		my \$out = \$ns / \$ds;		\$ns %= \$ds; 		\$out = ("0" x (length(\$ppow) - length(\$out) - 1)) . \$out;		print \$out;	} 	if ( \$p2 % 20 == 1) {		my \$g = Math::BigInt::bgcd(\$ds, \$ns);		\$ds /= \$g;		\$ns /= \$g;	}}`

## Perl 6

`# based on http://www.mathpropress.com/stan/bibliography/spigot.pdf sub stream(&next, &safe, &prod, &cons, \$z is copy, @x) {    gather loop {        \$z = safe(\$z, my \$y = next(\$z)) ??             prod(\$z, take \$y)          !!             cons(\$z, @x[(state \$)++])      }} sub extr([\$q, \$r, \$s, \$t], \$x) {    (\$q * \$x + \$r) div (\$s * \$x + \$t)} sub comp([\$q,\$r,\$s,\$t], [\$u,\$v,\$w,\$x]) {    [\$q * \$u + \$r * \$w,     \$q * \$v + \$r * \$x,     \$s * \$u + \$t * \$w,     \$s * \$v + \$t * \$x]} my @pi :=     stream -> \$z { extr(\$z, 3) },           -> \$z, \$n { \$n == extr(\$z, 4) },           -> \$z, \$n { comp([10, -10*\$n, 0, 1], \$z) },           &comp,           <1 0 0 1>,           (1..*).map: { [\$_, 4 * \$_ + 2, 0, 2 * \$_ + 1] } loop {    print @pi.shift;    once print '.'}`

## PicoLisp

The following script uses the spigot algorithm published by Jeremy Gibbons. Hit Ctrl-C to stop it.

`#!/usr/bin/picolisp /usr/lib/picolisp/lib.l (de piDigit ()   (job '((Q . 1) (R . 0) (S . 1) (K . 1) (N . 3) (L . 3))      (while (>= (- (+ R (* 4 Q)) S) (* N S))         (mapc set '(Q R S K N L)            (list               (* Q K)               (* L (+ R (* 2 Q)))               (* S L)               (inc K)               (/ (+ (* Q (+ 2 (* 7 K))) (* R L)) (* S L))               (+ 2 L) ) ) )      (prog1 N         (let M (- (/ (* 10 (+ R (* 3 Q))) S) (* 10 N))            (setq Q (* 10 Q)  R (* 10 (- R (* N S)))  N M) ) ) ) ) (prin (piDigit) ".")(loop   (prin (piDigit))   (flush) )`

Output:

`3.14159265358979323846264338327950288419716939937510582097494459 ...`

## PL/I

`/* Uses the algorithm of S. Rabinowicz and S. Wagon, "A Spigot Algorithm *//* for the Digits of Pi".                                                */(subrg, fofl, size):Pi_Spigot: procedure options (main);                 /* 21 January 2012. */   declare (n, len) fixed binary;    n = 1000;   len = 10*n / 3;   begin;      declare ( i, j, k, q, nines, predigit ) fixed binary;      declare x fixed binary (31);      declare a(len) fixed binary (31);       a = 2; /* Start with 2s */      nines, predigit = 0; /* First predigit is a 0 */      do j = 1 to n;         q = 0;         do i = len to 1 by -1; /* Work backwards */            x = 10*a(i) + q*i;            a(i) = mod (x, (2*i-1));            q = x / (2*i-1);         end;         a(1) = mod(q, 10); q = q / 10;         if q = 9 then nines = nines + 1;         else if q = 10 then            do;               put edit(predigit+1) (f(1));               do k = 1 to nines;                  put edit ('0')(a(1)); /* zeros */               end;               predigit, nines = 0;            end;         else            do;               put edit(predigit) (f(1)); predigit = q;               do k = 1 to nines; put edit ('9')(a(1)); end;               nines = 0;            end;      end;      put edit(predigit) (f(1));   end; /* of begin block */end Pi_Spigot;`

output:

```03141592653589793238462643383279502884197169399375105820974944592307816406286208
99862803482534211706798214808651328230664709384460955058223172535940812848111745
02841027019385211055596446229489549303819644288109756659334461284756482337867831
65271201909145648566923460348610454326648213393607260249141273724587006606315588
17488152092096282925409171536436789259036001133053054882046652138414695194151160
94330572703657595919530921861173819326117931051185480744623799627495673518857527
24891227938183011949129833673362440656643086021394946395224737190702179860943702
77053921717629317675238467481846766940513200056812714526356082778577134275778960
91736371787214684409012249534301465495853710507922796892589235420199561121290219
60864034418159813629774771309960518707211349999998372978049951059731732816096318
59502445945534690830264252230825334468503526193118817101000313783875288658753320
83814206171776691473035982534904287554687311595628638823537875937519577818577805
32171226806613001927876611195909216420198
```

## PureBasic

Calculate Pi, limited to ~24 M-digits for memory and speed reasons.

`#SCALE = 10000#ARRINT=  2000 Procedure Pi(Digits)  Protected First=#True, Text\$  Protected Carry, i, j, sum  Dim Arr(Digits)  For i=0 To Digits    Arr(i)=#ARRINT  Next  i=Digits  While i>0    sum=0    j=i    While j>0      sum*j+#SCALE*arr(j)      Arr(j)=sum%(j*2-1)      sum/(j*2-1)      j-1    Wend    Text\$ = RSet(Str(Carry+sum/#SCALE),4,"0")    If First      Text\$ = ReplaceString(Text\$,"3","3.")      First = #False    EndIf    Print(Text\$)    Carry=sum%#SCALE    i-14  WendEndProcedure If OpenConsole()  SetConsoleCtrlHandler_(?Ctrl,#True)   Pi(24*1024*1024)EndIfEnd Ctrl:PrintN(#CRLF\$+"Ctrl-C was pressed")End`

## Python

`def calcPi():    q, r, t, k, n, l = 1, 0, 1, 1, 3, 3    while True:        if 4*q+r-t < n*t:            yield n            nr = 10*(r-n*t)            n  = ((10*(3*q+r))//t)-10*n            q  *= 10            r  = nr        else:            nr = (2*q+r)*l            nn = (q*(7*k)+2+(r*l))//(t*l)            q  *= k            t  *= l            l  += 2            k += 1            n  = nn            r  = nr import syspi_digits = calcPi()i = 0for d in pi_digits:    sys.stdout.write(str(d))    i += 1    if i == 40: print(""); i = 0`
output
```3141592653589793238462643383279502884197
1693993751058209749445923078164062862089
9862803482534211706798214808651328230664
7093844609550582231725359408128481117450
2841027019385211055596446229489549303819
6442881097566593344612847564823378678316
5271201909145648566923460348610454326648
2133936072602491412737245870066063155881
7488152092096282925409171536436789259036
0011330530548820466521384146951941511609
4330572703657595919530921861173819326117
...
```

## Racket

The first 200 digits using bigfloats. Since the argument to bf-precision it the number of binary digits, a small computation is needed to calculate how many binary digits are the same as 200 decimal digits.

` #lang racket(require math/bigfloat)(bf-precision (exact-floor (/ (* 200 (log 10)) (log 2))))pi.bf `

## REXX

Calculate digits of π (pi) using John Machin's formula.

It should be noted that this mechanism spits out the next (new) digits of π, not just a single digit.
It will spit out as many (new) digits of π that it finds.

The following REXX program uses the formula:

```                    ┌─   ─┐                ┌─     ─┐
π                 │  1  │                │   1   │           John
───  =   4 ∙ arctan│ ─── │     -    arctan│ ───── │             Machin's
4                 │  5  │                │  239  │               formula
└─   ─┘                └─     ─┘

which expands into:

┌─                                                                      ─┐
│    1         1          1          1          1           1            │
4 ∙  │   ───  -  ──────  +  ──────  -  ──────  +  ──────  -  ────────  +  ... │
│     1         3          5          7          9           11          │
│  1∙5       3∙5        5∙5        7∙5        9∙5        11∙5            │
└─                                                                      ─┘

┌─                                                                      ─┐
│    1         1          1          1          1           1            │
-   │   ───  -  ──────  +  ──────  -  ──────  +  ──────  -  ────────  +  ... │
│      1         3          5          7          9           11         │
│ 1∙239     3∙239      5∙239      7∙239      9∙239      11∙239           │
└─                                                                      ─┘
```
`/*REXX program to spit out pi digits (few at a time) until  Ctrl-Break. */ arg digs .; if digs=='' then digs=1e6  /*allow the specification of digs*/fn='PI_DIGITS.OUT'                     /*file that can be written to.   */numeric digits digs                    /*big digs, the slower the spits.*/pi=0;  s=16;  r=4;  v=5;  vs=v*v;  g=239;  gs=g*g;  old=;  spewed=0;  j=1call time 'E' /*─────────────────────────────────────John Machin's formula for  pi.   */  do n=1  by 2  pi=pi + s/(n*v) - r/(n*g)  if pi==old  then leave               /*no further with current DIGITS.*/  s=-s;  r=-r;  v=v*vs;  g=g*gs  if n\==1  then do j=spewed+1  to compare(pi,old)                 spit=substr(pi,j,1)                 call charout   ,spit          /*spit out 1 digit of pi.*/                 call charout fn,spit          /* ...and also to a file.*/                 end  spewed=j-1  old=pi  end   /*n*/ say;    say  n%2+1   'iterations took'   format(time("E"),,2)   'seconds.'                                       /*stick a fork in it, we're done.*/`

output (until the   Ctrl-Break   key was pressed):

```3.141592653589793238462643383279402884197179499374105820974944592307816406286108998628034825341117067982148086513282306647093844609550582231725359408128481117450284002701938521105559644622948954920381
96442981097566593344612847564823388678316527110190914564856692346034861045432664821339360726024914127372459700660631568817488152092096282925409171536436799269035001132053054982046652138414695194151160
94330572703657595919530921861173819326118931051185480744623899627595673518857527249912279381830119491398336733624406566420860213949463952247371907021898609437027705392171762931767523846748184676794051
31000568127145263560827785771342757799609173637178721468430801225953430146559585370050892279789258923542029956012128021960863034418159813629774771319960518707211349999998372978049941059731732816096218
59402445945534690830264251230825334468503526193118817000000313783875288658753310838142061717766914730359825349042875546873116956286388235388769375295778185878053217122680661200192787661119590921642019
89380952572000654858632788659361533818289682303019510353018529699958736225994138912597217752834791315155748572424541506969508395330168617278558890750983817546374649393192550604009277016711390098488240
12858361603563707650104700181942955596199946768837459448255389774726847104047534646208046684259079491293313677029989152104752162056966024057038150193511253382420035587640247496473263914299272604269922
79678235478163500934172164121992458631502028618297455570675983850549458858692799569092720079750920295532116534498720275595023648066549912988183479775356636980742654252786255181841757467289098777289380
00816470600161452491921732172147723401414419735685481613611573525521334757418494684385233239073941433345477624168625189835695855620992192221842725502542568976717905946016534668059886272327917860857843
83827967976681454000953883786360950680064225125205117393984896084128488626945604241965285022200661186306744278622049194944047123713886950956364371917287467764657573962413990865832646995813390478027590
19946576407895126946839835259560982582262052248940772671947826848250147699090264013639443745530506820349625245174939965143142980919065925093722169646151571985838741069788595977297549892016175392846813
82686838789427741569918559252469539594310599725246808459872736446958486538367362226260991246080512438843904412441365597627807977156914359977001296160894416958685558484063534210722258285886481584560284
06016842749452267467678995252138522559954666727823986456595116354986220577456498035593634568174324112515076069479441096596094025228889710893145669136867228749940560001403208617928680920874760917824938
58900971490967598526136554978199312978481168299994872265880485756301427047755513237964145152374623436454285844489526586781105114135473574952311342716610213596953622144295248493718711014576540369027993
44037420073105785390622983974478084785896833114457138697519435064302184521900484810053706146806749192781912979399510614196634287544406437451237181921899983900159195618146751426912497489409071864942319
61567945208095146550225231603881930141093762137856956639938787083039079791077346722182562599661401421403068038447734549202605414665925101497442850732518665002132434088190700486331734649651453905796268
56000550810665879799816357473638405257145910299706413010097120628043904976951567715770041033786993600723055976317636942187212514712053292819182618612586722158929841484882916446060957527069572209175671
16722900981690915280173506712748583222871835209354965725121083579151379881091444200067500334671003141267011379908658516498315019701651511685171437657618351556508849099998599823873455283216355076489185
3589322618548963213293308985706410467525907091548141654985946163718027098199431992448895757128289069232332609729971208443357326549938239129325974636672058350414281388303103824903758985243745
```

## Ruby

### using agm

` # Calculate Pi using the Arithmetic Geometric Mean of 1 and 1/sqrt(2)###  Nigel_Galloway#  March 8th., 2012.#require 'flt'Flt::BinNum.Context.precision = 8192a = n = 1g = 1 / Flt::BinNum(2).sqrtz = 0.25(0..17).each{  x = [(a + g) * 0.5, (a * g).sqrt]  var = x[0] - a  z -= var * var * n  n += n  a = x[0]  g = x[1]}puts a * a / z `

Produces:

```3.141592653589793238462643383279502884197169399375105820974944592307816406286208
99862803482534211706798214808651328230664709384460955058223172535940812848111745
02841027019385211055596446229489549303819644288109756659334461284756482337867831
65271201909145648566923460348610454326648213393607260249141273724587006606315588
17488152092096282925409171536436789259036001133053054882046652138414695194151160
94330572703657595919530921861173819326117931051185480744623799627495673518857527
24891227938183011949129833673362440656643086021394946395224737190702179860943702
77053921717629317675238467481846766940513200056812714526356082778577134275778960
91736371787214684409012249534301465495853710507922796892589235420199561121290219
60864034418159813629774771309960518707211349999998372978049951059731732816096318
59502445945534690830264252230825334468503526193118817101000313783875288658753320
83814206171776691473035982534904287554687311595628638823537875937519577818577805
32171226806613001927876611195909216420198938095257201065485863278865936153381827
96823030195203530185296899577362259941389124972177528347913151557485724245415069
59508295331168617278558890750983817546374649393192550604009277016711390098488240
12858361603563707660104710181942955596198946767837449448255379774726847104047534
64620804668425906949129331367702898915210475216205696602405803815019351125338243
00355876402474964732639141992726042699227967823547816360093417216412199245863150
30286182974555706749838505494588586926995690927210797509302955321165344987202755
96023648066549911988183479775356636980742654252786255181841757467289097777279380
00816470600161452491921732172147723501414419735685481613611573525521334757418494
68438523323907394143334547762416862518983569485562099219222184272550254256887671
79049460165346680498862723279178608578438382796797668145410095388378636095068006
42251252051173929848960841284886269456042419652850222106611863067442786220391949
45047123713786960956364371917287467764657573962413890865832645995813390478027590
09946576407895126946839835259570982582262052248940772671947826848260147699090264
01363944374553050682034962524517493996514314298091906592509372216964615157098583
87410597885959772975498930161753928468138268683868942774155991855925245953959431
04997252468084598727364469584865383673622262609912460805124388439045124413654976
27807977156914359977001296160894416948685558484063534220722258284886481584560285
06016842739452267467678895252138522549954666727823986456596116354
```

### translation of Icon

Translation of: Icon
`def pi  q, r, t, k, n, l = 1, 0, 1, 1, 3, 3  dot = nil  loop do    if 4*q+r-t < n*t      yield n      if dot.nil?         yield '.'        dot = '.'      end      nr = 10*(r-n*t)      n = ((10*(3*q+r)) / t) - 10*n      q *= 10      r = nr    else      nr = (2*q+r) * l      nn = (q*(7*k+2)+r*l) / (t*l)      q *= k      t *= l      l += 2      k += 1      n = nn      r = nr    end  endend pi {|digit| print digit; \$stdout.flush}`

## Scala

`object Pi {  class PiIterator extends Iterable[BigInt]{    var r:BigInt=0    var q, t, k:BigInt=1    var n, l:BigInt=3    var nr, nn:BigInt=0     def iterator: Iterator[BigInt]=new Iterator[BigInt]{      def hasNext=true      def next():BigInt={        while((4*q+r-t) >= (n*t)) {          nr = (2*q+r)*l          nn = (q*(7*k)+2+(r*l))/(t*l)          q = q * k          t = t * l          l = l + 2          k = k + 1          n  = nn          r  = nr			        }        val ret=n        nr = 10*(r-n*t)        n  = ((10*(3*q+r))/t)-(10*n)        q  = q * 10        r  = nr        ret      }    }  }   def main(args: Array[String]): Unit = {    val it=new PiIterator    println((it head) + "." + (it take 300 mkString))  }}`

Output:

```3.141592653589793238462643383279502884197169399375105820974944592307816406286208998
62803482534211706798214808651328230664709384460955058223172535940812848111745028410
27019385211055596446229489549303819644288109756659334461284756482337867831652712019
09145648566923460348610454326648213393607260249141273```

## Seed7

`\$ include "seed7_05.s7i";  include "bigint.s7i"; const proc: main is func  local    var bigInteger: q is 1_;    var bigInteger: r is 0_;    var bigInteger: t is 1_;    var bigInteger: k is 1_;    var bigInteger: n is 3_;    var bigInteger: l is 3_;    var bigInteger: nn is 0_;    var bigInteger: nr is 0_;    var boolean: first is TRUE;  begin    while TRUE do      if 4_ * q + r - t < n * t then        write(n);        if first then          write(".");          first := FALSE;        end if;        nr := 10_ * (r - n * t);        n := 10_ * (3_ * q + r) div t - 10_ * n;        q *:= 10_;        r := nr;        flush(OUT);      else        nr := (2_ * q + r) * l;        nn := (q * (7_ * k + 2_) + r * l) div (t * l);        q *:= k;        t *:= l;        l +:= 2_;        incr(k);        n := nn;        r := nr;      end if;    end while;  end func;`

Original source: [4]

## Tcl

Based on the reference in the D code.

Works with: Tcl version 8.6
`package require Tcl 8.6 # http://www.cut-the-knot.org/Curriculum/Algorithms/SpigotForPi.shtml# http://www.mathpropress.com/stan/bibliography/spigot.pdfproc piDigitsBySpigot n {    yield [info coroutine]    set A [lrepeat [expr {int(floor(10*\$n/3.)+1)}] 2]    set Alen [llength \$A]    set predigits {}    while 1 {	set carry 0	for {set i \$Alen} {[incr i -1] > 0} {} {	    lset A \$i [expr {		[set val [expr {[lindex \$A \$i] * 10 + \$carry}]]		% [set modulo [expr {2*\$i + 1}]]	    }]	    set carry [expr {\$val / \$modulo * \$i}]	}	lset A 0 [expr {[set val [expr {[lindex \$A 0]*10 + \$carry}]] % 10}]	set predigit [expr {\$val / 10}]	if {\$predigit < 9} {	    foreach p \$predigits {yield \$p}	    set predigits [list \$predigit]	} elseif {\$predigit == 9} {	    lappend predigits \$predigit	} else {	    foreach p \$predigits {yield [incr p]}	    set predigits [list 0]	}    }}`

The pi digit generation requires picking a limit to the number of digits; the bigger the limit, the more digits can be safely computed. A value of 10k yields values relatively rapidly.

`coroutine piDigit piDigitsBySpigot 10000fconfigure stdout -buffering nonewhile 1 {    puts -nonewline [piDigit]}`