Description

给你一个四位数a，有可能含前导0，要你执行这样的操作。 取得a的平方数v。 若v不足八位，则加前导0变成8位。 取这8位数的中间四位重新赋值给a，再转到步骤1，如此循环。 现问你通过这样的操作，可得到多少种不同的四位数，包含前导0的也算四位数，如0015也算一种，初始的a也算一种。

Input

输入包括多组测试数据。每组数据包含一个四位数a。

Output

对于每组数据，输出由a产生的不同四位数的个数。

Sample

Input

0001
5555
0815
6239

Output

2
32
17
111