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

题目描述

背景
在Divido星球上，教师们面临一个严重的问题。由于计算器的普及，学生们不再会用纸笔进行长除法运算。然而，该星球政府宣布将对所有基础学校的学生进行数学能力测试。由于这是一项选择题测试，学生只需计算两个数相除时循环周期的长度即可。你的任务是编写一个程序，提前计算出正确的解，以便于批改试卷。此外，Divido星球上的不同智慧物种拥有的手指数量不同，因此他们的数字系统基数也不同，这带来了额外的问题。

问题
给定一个基数$b$、分子$x$和分母$y$（后两者均为基数为$b$的整数），计算分数$q = x/y$在基数为$b$的展开式中循环周期的长度。记住，有理数$q$的基数为$b$的展开式的数字是基数的幂的系数：

$$q = q_n q_{n-1} \dots q_0 . q_{-1} q_{-2} \dots = \sum_{i=-\infty}^n q_i b^i $$

以下是一些例子：

• $110 / 210 = 0.510$
• $13 / 103 = 0.13$
• $210 / 1110 = 0.181818 \dots_{10} = 0.(18)_{10}$

在前两个例子中，分数的基数$b$展开式是有限的，意味着后续所有数字均为零。在这种情况下，我们说循环周期的长度为$0$。注意，第一个例子也可以表示为$0.4(9)_{10}$，其周期长度为$1$，但这并不是我们想要的结果。

在第三个例子中，循环周期的长度明确为$2$。

输入
第一行包含分数的数量。对于每个分数，首先给出基数$b$（以十进制表示，$2 \leq b \leq 36$），然后是分子$x$和分母$y$（以基数为$b$表示），三者之间用空格分隔。保证分母满足$0 < y \leq 100000_{10}$。超出$0 \dots 9$范围的数字用字母表示（从"a"或"A"开始，大小写不敏感）。

输出
每个场景的输出以一行"Scenario #i:"开始，其中$i$是场景编号（从$1$开始）。然后输出一行，包含$x/y$在基数为$b$的展开式中循环周期的长度（以十进制表示）。每个场景的输出以空行结束。

示例输入

4
10 1 2
3 1 10
10 2 11
36 HI ho

示例输出

Scenario #1:
0

Scenario #2:
0

Scenario #3:
2

Scenario #4:
13

来源
TUD Programming Contest 2004, Darmstadt, Germany