Instead of finding all divisors of N (which takes $$$O(\sqrt{N})$$$ time and causes TLE for $$$N=10^{18}$$$), we recursively divide N by Fibonacci numbers.

To avoid counting permutations multiple times, we enforce an ordering constraint: we only use Fibonacci numbers from a certain index onwards, ensuring each factorization is counted exactly once.

Algorithm: 1. Precompute all Fibonacci numbers ≤ $$$10^{18}$$$ 2. Use recursive DP with memoization: dp(N, idx) = number of ways to factorize N using Fibonacci numbers from index idx onwards 3. For each Fibonacci number at index idx: — Option 1: Skip it and move to idx + 1 — Option 2: If it divides N, use it and recurse on N / fib[idx] (same index to allow repetition)

Time Complexity: $$$O(T \cdot \text{Fib_count}^2 \cdot \log N)$$$ due to memoization
Space Complexity: $$$O(\text{Fib_count} \cdot \log N)$$$ for memoization table

#include <iostream>
#include <vector>
#include <map>

using namespace std;

vector<long long> fibs;
map<pair<long long, int>, long long> memo;

void precompute() {
    long long a = 1, b = 2;
    // Generate Fibonacci numbers > 1 up to 10^18
    // Sequence starts: 2, 3, 5, 8, 13...
    fibs.push_back(b);
    while (true) {
        long long next_fib = a + b;
        if (next_fib > 1e18) break;
        fibs.push_back(next_fib);
        a = b;
        b = next_fib;
    }
}

// Top-Down DP: count ways to factorize N using fibs[idx..end]
long long dp(long long N, int idx) {
    // Base case: N reduced to 1 = found 1 valid factorization
    if (N == 1) return 1;
    
    // No Fibonacci numbers left but N > 1 = invalid path
    if (idx >= fibs.size()) return 0;
    
    // Check memoization
    if (memo.count({N, idx})) return memo[{N, idx}];
    
    long long ways = 0;
    
    // Option 1: Don't use fibs[idx], move to next Fibonacci
    ways += dp(N, idx + 1);
    
    // Option 2: Use fibs[idx] if it divides N
    // Keep same idx to allow using this Fibonacci multiple times
    if (N % fibs[idx] == 0) {
        ways += dp(N / fibs[idx], idx);
    }
    
    return memo[{N, idx}] = ways;
}

void solve() {
    long long N;
    cin >> N;
    cout << dp(N, 0) << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    precompute();
    
    int t;
    if (cin >> t) {
        while (t--) solve();
    }
    return 0;
}

By Carmichael's theorem, large Fibonacci numbers (except 2, 3, 8, 144) contain unique prime factors not found in smaller Fibonacci numbers.

This means: - If N is divisible by a large Fibonacci number, we must use it in the factorization - We greedily divide N by large Fibonacci numbers first - After this greedy phase, N becomes a product of powers of 2 and 3 only - We count valid combinations of {2, 3, 8, 144}

Algorithm: 1. Generate Fibonacci numbers, excluding 2, 3, 8, 144 (the "exception" numbers) 2. Greedily divide N by large Fibonacci numbers (from largest to smallest) 3. Factorize remaining N into $$$2^p \times 3^q$$$ 4. Count ways to form $$$2^p \times 3^q$$$ using {2, 3, 8, 144}: — Iterate over count of 144 used (each 144 = $$$2^4 \times 3^2$$$) — Remaining power of 2 must be formed using {2, 8} — Number of ways to form remaining power P of 2: $$$\lfloor P/3 \rfloor + 1$$$

Time Complexity: Nearly $$$O(\log N)$$$ per query
Space Complexity: $$$O(\text{Fib_count})$$$

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<long long> greedy_fibs;

void precompute() {
    long long f[90];
    f[1] = 1; f[2] = 1;
    
    // Generate Fibonacci sequence up to 10^18
    for (int i = 3; i <= 87; i++) {
        f[i] = f[i-1] + f[i-2];
        
        // Exclude exceptions: F_3=2, F_4=3, F_6=8, F_12=144
        // These don't have unique prime factors
        if (i != 3 && i != 4 && i != 6 && i != 12) {
            greedy_fibs.push_back(f[i]);
        }
    }
    
    // Sort in descending order for greedy approach
    sort(greedy_fibs.rbegin(), greedy_fibs.rend());
}

void solve() {
    long long N;
    cin >> N;
    
    // Step 1: Greedily divide N by large Fibonacci numbers
    // (they have unique prime factors, so MUST be used if they divide N)
    for (long long fib : greedy_fibs) {
        while (N % fib == 0) {
            N /= fib;
        }
    }
    
    // Step 2: Factorize remaining N into 2^p * 3^q
    long long p = 0, q = 0;
    while (N % 2 == 0) { p++; N /= 2; }
    while (N % 3 == 0) { q++; N /= 3; }
    
    // If remainder is not 1, it has other prime factors → impossible
    if (N != 1) {
        cout << 0 << "\n";
        return;
    }
    
    // Step 3: Count combinations using {2, 3, 8, 144}
    // where: 144 = 2^4 * 3^2, 8 = 2^3, 3 = 3^1, 2 = 2^1
    long long ans = 0;
    
    // Try all possible counts of 144
    for (long long c144 = 0; c144 * 4 <= p && c144 * 2 <= q; c144++) {
        
        // Remaining power of 2 after using c144 copies of 144
        long long P_remaining = p - c144 * 4;
        
        // Ways to form P_remaining using 8 (2^3) and 2 (2^1)
        // This is: how many ways to write P as sum of 3's and 1's
        ans += (P_remaining / 3) + 1;
    }
    
    cout << ans << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    precompute();
    
    int t;
    if (cin >> t) {
        while (t--) solve();
    }
    return 0;
}