Find Position in Monotone Sequence

Problem Statement

Find Position in Monotone Sequence Three coefficients a , b and c fix an infinite sequence f_1, f_2, f_3, ... of integers: f_1 = 1 for every k > 1 : f_k = a f_[k/2] + b floor(log2(k)) + c * k Here [k/2] is integer division (the floor of k / 2 ), and floor(log2(k)) is the base-2 logarithm rounded down — equivalently, one less than the number of binary digits of k . Since a >= 1 , b >= 1 and c >= 0 , the sequence never decreases. When c >= 1 it strictly increases; when c = 0 neighbouring terms may be equal. For each query you are given a , b , c and a positive integer X . Report the smallest index k with 1 <= k <= 10^18 and f_k = X . If no such index exists, report 0 . Input Format The first line contains one integer T , the number of queries. Each of the next T lines contains four space-separated integers a , b , c and X . Output Format Print T lines. Line i must read #i followed by a single space and the answer for query i . Constraints 1 <= T <= 650 1 <=