题目描述

设${x} = 0.a_1a_2a_3...$为有理数$z$的小数部分的二进制表示。假设${x}$是循环的，那么我们可以将其写为

{x} = 0.a₁a₂...a_r(a_r+1a_r+2...a_r+s)^w

其中$r$和$s$为整数，满足$r \geq 0$且$s > 0$。此外，$(a_{r+1}a_{r+2}...a_{r+s})^w$表示${x}$的一个无限重复的二进制子序列。

子序列$x_1 = a_1a_2 ... a_r$被称为${x}$的前周期，而$x_2 = a_{r+1}a_{r+2} ... a_{r+s}$则是${x}$的周期。

若选择$|x_1|$和$|x_2|$尽可能小，则$x_1$称为最小前周期，$x_2$称为${x}$的最小周期。

例如，$x = 1/10 = 0.0001100110011(00110011)^w$，其中$0001100110011$是$1/10$的一个前周期，$00110011$是一个周期。

然而，我们也可以将$1/10$写为$1/10 = 0.0(0011)^w$，此时$0$是最小前周期，$0011$是$1/10$的最小周期。

$1/10$的最小周期从二进制小数点右侧第2位开始，最小周期的长度为4。

编写一个程序，找出小于1的正有理数的小数部分在二进制表示下的最小周期的第一个比特的位置，以及最小周期的长度，其中前周期也取最小值。

输入

每一行是一个测试用例，表示一个有理数$p/q$，其中$p$和$q$为整数，且$p \geq 0$，$q > 0$。

输出

每一行对应一个测试用例，输出一个数对，第一个数是最小周期的第一个比特的位置，第二个数是该有理数的最小周期的长度。

输入样例 1

1/10
1/5
101/120
121/1472

输出样例 1

Case #1: 2,4
Case #2: 1,4
Case #3: 4,4
Case #4: 7,11

来源

Manila 2006