http://codeforces.com/gym/100548/attachments

Time limit 1000 ms Memory limit 262144 kB

Description

Given two integers A and B. Sequence S is defined as follow:
• S0 = A
• S1 = B
• Si = |Si−1 − Si−2| for i ≥ 2
Count the number of distinct numbers in S.

Input

The first line of the input gives the number of test cases, T. T test cases follow. T is about 100000. Each test case consists of one line - two space-separated integers A, B. (0 ≤ A, B ≤ 10^18).

Output

For each test case, output one line containing “Case #x: y”, where x is the test case number (starting from 1) and y is the number of distinct numbers in S.

Sample Input

2
7 4
3 5

Sample Output

Case #1: 6
Case #2: 5

Problem solving:

找规律，模拟演算过程。例如a = S0 = 10, b = s1 = 3; 
s2 = 7, s3 = 4, s4 = 3, s5 = 1。先看这里10 7 4 1分别是10 - 3t的到的结果，能减10/3 = 3次。这3代表10 7 4这三个数。接下来相当于变成s0 = b = 3, s1 = a%b = 1 重新循环上述操作。

#include <stdio.h>
long long ans;
void gcd(long long a, long long b)
{
	if (!b)
		return ;
	ans += a / b;
	gcd(b, a % b);
}
int main()
{
	int t;
	long long a, b;
	scanf("%d", &t);
	for (int i = 1; i <= t; i++)
	{
		ans = 1;
		scanf("%lld%lld", &a, &b);
		if (!a && b || a && !b)
			ans++;
		gcd(a, b);
		printf("Case #%d: %lld\n", i, ans);
	}
	return 0;
}