本题没有可用的提交语言。

题目描述

农夫约翰喜欢帮助奶牛提升数学能力。他承诺，如果奶牛能解决各种数学问题，就给它们干草味的冰淇淋。

他对贝西说：“选一个六位整数，告诉我它是多少。然后提取中间四位数字，将它们平方，去掉高位数字直到得到一个六位或更短的数，告诉我结果。”

贝西是一位隐藏的数学天才，她选择了六位数字 655554。“哞：6 5 5 5 5 4，” 她说。然后她提取中间四位数字：5555，将其平方得到 30858025，只保留最后六位数字 858025。“哞：8 5 8 0 2 5，” 她回答约翰。

约翰明智地点头，认可贝西的算术能力。“现在继续这个过程，直到遇到一个已经出现过的数字，” 他要求道。 贝西决定最好创建一个表格来记录所有步骤：

Middle Middle Shrunk to

   Num   4 digits   square   6 or fewer

 655554    5555    30858025    858025

 858025    5802    33663204    663204

 663204    6320    39942400    942400

 942400    4240    17977600    977600

 977600    7760    60217600    217600 <-+

 217600    1760     3097600     97600   |

  97600    9760    95257600    257600   |

 257600    5760    33177600    177600   |

 177600    7760    60217600    217600 --+

贝西将表格展示给约翰，约翰微笑着端出一大盘美味的干草冰淇淋。“没错，贝西，” 他称赞道。“这个序列在四个数字的循环中重复，第一个遇到的循环数字是 217600。经过 9 次迭代后检测到循环。”

请帮助其他奶牛赢取冰淇淋奖励。给定一个六位数字，计算检测到循环所需的总迭代次数、遇到的第一个循环数字，以及循环的长度。

约翰想知道贝西是否知道所有的技巧。他曾制作过一个表格帮助她，但她从未问过：

Middle Middle Shrunk to

   Num   4 digits   square   6 or fewer

 200023    0002       4        4

      4       0       0        0

      0       0       0        0         [a self-loop]

其结果为：检测到循环需要 3 次迭代，循环数字为 0，循环长度为 1。

注意：你的程序使用的内存不得超过 16MB。

输入

第 1 行：一个六位整数，作为序列测试的起始数字。

输出

第 1 行：三个空格分隔的整数：循环的第一个数字、循环长度、检测到循环的最小迭代次数。

输入数据 1

655554

输出数据 1

217600 4 9