← 返回题目列表

Codeforces · 182/D

D. 公约数

中文机器翻译题面 查看原题

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”的除数。