Vasya 最近在学校学习了数字的除数是什么,并决定确定字符串的除数。这是他的想法。
字符串 a 是字符串 b 的除数当且仅当存在一个正整数 x,这样如果我们连续写出字符串 a x 次,我们就得到字符串 b。例如,字符串“abab”有两个除数 - “ab”和“abab”。
现在 Vasya 想要编写一个程序来计算两个字符串的公约数。请帮助他。
输入
第一个输入行包含一个非空字符串 s1。
第二个输入行包含一个非空字符串 s2。
字符串s1和s2的长度均为正数且不超过105。字符串仅由小写拉丁字母组成。
输出
打印字符串 s1 和 s2 的公约数数。
示例
输入 #1
abcdabcd abcdabcdabcdabcd
输出 #1
2
输入 #2
aaa aa
输出 #2
1
注意
在第一个示例中,公约数是字符串“abcd”和“abcdabcd”。
在第二个示例中,公约数是单个字符串“a”。字符串“aa”不包含在答案中,因为它不是字符串“aaa”的除数。