Tuples[n_,k_]:=Table[IntegerDigits[i,k,n],{i,0,k^n-1}]
diff[{{a_},{b_},___}]:=b-a
Position[FAEvolveList[fa,1,#,10],#]&/@Tuples[4,2]
{{{1},{9}},{{1},{9}},{{1},{9}},{{1},{9}},{{1},{9}},{{1},{9}},{{1},{9}},{{1},{9}},{{1},{9}},{{1},{9}},{{1},{9}},{{1},{9}},{{1},{9}},{{1},{9}},{{1},{9}},{{1},{9}}}
Position[FAEvolveList[fa,2,#,10],#]&/@Tuples[4,2]
{{{1},{5},{9}},{{1},{5},{9}},{{1},{5},{9}},{{1},{5},{9}},{{1},{5},{9}},{{1},{5},{9}},{{1},{5},{9}},{{1},{5},{9}},{{1},{5},{9}},{{1},{5},{9}},{{1},{5},{9}},{{1},{5},{9}},{{1},{3},{5},{7},{9},{11}},{{1},{3},{5},{7},{9},{11}},{{1},{2},{3},{4},{5},{6},{7},{8},{9},{10},{11}},{{1},{2},{3},{4},{5},{6},{7},{8},{9},{10},{11}}}
ElementOrder[rule_,s0_,width_,t_,k_:2]:=Apply[LCM,diff[Position[FAEvolveList[rule,s0,#,t],#]]&/@Tuples[width,k]]
Apply[LCM,diff[Position[FAEvolveList[fa,1,#,10],#]]&/@Tuples[7,2]]
8
Position[FAEvolveList[fa,2,#,10],#]&/@Tuples[7,2]
{{{1},{5},{9}},{{1},{5},{9}},{{1},{5},{9}},{{1},{5},{9}},{{1},{5},{9}},{{1},{5},{9}},{{1},{5},{9}},{{1},{5},{9}},{{1},{5},{9}},{{1},{5},{9}},{{1},{5},{9}},{{1},{5},{9}},{{1},{3},{5},{7},{9},{11}},{{1},{3},{5},{7},{9},{11}},{{1},{2},{3},{4},{5},{6},{7},{8},{9},{10},{11}},{{1},{2},{3},{4},{5},{6},{7},{8},{9},{10},{11}}}
ElementOrder[fa,1,10,30]
16
Table[ElementOrder[fa,1,w,30],{w,10}]
{2,4,4,8,8,8,8,16,16,16}
Table[ElementOrder[fa,2,w,30],{w,10}]
{1,2,4,4,8,8,8,8,16,16}
ListPlot[%,PlotJoinedTrue];