R109584557

// Problem: Fibonacci的复仇 Revenge of Fibonacci
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/UVA12333
// Memory Limit: 0 MB
// Time Limit: 10000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;

struct NewInt
{
	int BASE = 100000000;
	int WIDTH = 8;
	vector<int> s;
	NewInt operator = (const string& str)
	{
		s.clear();
		int x, len = (str.length() - 1) / WIDTH  + 1;
		for (int i = 0; i < len; i++)
		{
			int end = str.length() - i * WIDTH;
			int start = max(0, end - WIDTH);
			sscanf(str.substr(start, end - start).c_str(), "%d", &x);
			s.push_back(x);
		}
		return *this;
	}
	NewInt operator + (const NewInt& b) const
	{
		NewInt c;
		c.s.clear();
		for (int i = 0, g = 0; ; i++)
		{
			if (g == 0 && i >= s.size() && i >= b.s.size())
			{
				break;
			}
			int x = g;
			if (i < s.size())
			{
				x += s[i];
			}
			if (i < b.s.size())
			{
				x += b.s[i];
			}
			c.s.push_back(x % BASE);
			g = x / BASE;
		}
		return c;
	}

	bool operator % (const NewInt& b) const
	{
		int len = b.s.size();
		for (int i = len - 1; i >= 0; i--)
		{
			if (s[i] != b.s[i])
			{
				// printf("%d %d\n", buf[j], buf2[j]);
				return false;
			}
		}
		return true;
	}
};

int main()
{
	int T;
	cin >> T;
	string tmp;
	
	NewInt fibnacci[100005];
	fibnacci[0] = "1";
	fibnacci[1] = "1";
	for (int j = 2; j <= 100000; j++)
	{
		fibnacci[j] = fibnacci[j - 1] + fibnacci[j - 2];
	}
	for (int i = 1; i <= T; i++)
	{
		bool flag = 0;
		cin >> tmp;
		NewInt headtmp;
		headtmp = tmp;
		for (int j = 0; j <= 100000; j++)
		{
			if (headtmp % fibnacci[j])
			{
				printf("Case #%d: %d\n", i, j);
				flag = 1;
				break;
			}
		}
		if (!flag)
		{
			printf("Case #%d: %d\n", i, -1);
		}
	}
}