# Update: 222 strokes by using a bareword and (for the fun of it) support up to undecillion 10^36 (costs no extra chars due to bareword trick)
for f in 0 4 12 99 1024 1000024 999999999999999999999999999999999; do echo $f | \
perl -E'@x=a33544355436688779880066555766=~/./g;$_=<>;chop;while(($a=$_)-4){split//,b999aabb87780;$x=4*!$_;$x+=hex(pop@_)*!!-$&+!!$1*($x[$1]+7)+$x[$2+20]+$x[$3]while s/(.??)([^1]?)(1?.)$//;say"$a is $x.";$_=$x}say"4 is magic."' ; \
echo; done

# Update: 224 strokes by including the suggested =~/./g shortcut and moving output around a bit
perl -E'@x="033544355436688779880066555766"=~/./g;$_=<>;chop;while(($a=$_)-4){split//,"99aabb87780";$x=4*!$_;$x+=hex(pop@_)*!!-$&+!!$1*($x[$1]+7)+$x[$2+20]+$x[$3]while s/(.??)([^1]?)(1?.)$//;say"$a is $x.";$_=$x}say"4 is magic."'

# Update: 229 strokes by moving some conditionals into the regex
perl -E'@x=split//,"033544355436688779880066555766";$_=<>;chop;print;while($_-4){split//,"99aabb87780";$x=4*!$_;$x+=hex(pop@_)*!!-$&+!!$1*($x[$1]+7)+$x[$2+20]+$x[$3]while s/(.??)([^1]?)(1?.)$//;say" is $x.";print$_=$x}say" is magic."'

# Update: Ah, ha! 239 strokes:  !!-$& will do it
perl -E'@x=split//,"0335443554366887798866555766";$_=<>;chop;print;while($_-4){split//,"99aabb87780";$x=4*!$_;$x+=hex(pop@_)*!!-$&+!!$1*($x[$1]+7)+($2>1?$x[$2+18]+$x[$3]:$x[$2.$3])while s/(.??)(.?)(.)$//;say" is $x.";print$_=$x}say" is magic."'

# Update: 242 strokes, and works :), stealing some ideas from haarg & thundergnat
perl -E'@x=split//,"0335443554366887798866555766";$_=<>;chop;print;while($_-4){split//,"99aabb87780";$x=4*!$_;$x+=hex(pop@_)*!!(0+$&)+!!$1*($x[$1]+7)+($2>1?$x[$2+18]+$x[$3]:$x[$2.$3])while s/(.??)(.?)(.)$//;say" is $x.";print$_=$x}say" is magic."'

# Update: Down to 258 strokes
perl -E'@x=split//,"0335443554366887798866555766";$_=<>;chop;print;while($_!=4){split//,"99aabb87780";$_?do{$x=0;while(s/(.??)(.?)(.)$//){$x+=hex(pop@_)*(0+$&?1:0)+($1?$x[$1]+7:0)+($2>1?$x[$2+18]+$x[$3]:$x[$2.$3])}}:($x=4);say" is $x.";print$_=$x}say" is magic."'

# 261 strokes:
perl -E'@x=split//,"0335443554366887798866555766";$_=<>;chop;print;while($_!=4){@m=split//,"99aabb87780";$_?do{$x=0;while(s/(.??)(.?)(.)$//){$x+=hex(pop@m)*(0+$&?1:0)+($1?$x[$1]+7:0)+($2>1?$x[$2+18]+$x[$3]:$x[$2.$3])}}:($x=4);say" is $x.";print$_=$x}say" is magic."'

999999999999999999999999999999999 is 321.
321 is 21.
21 is 9.
9 is 4.
4 is magic.