Fast counting

$f( X ) $ means sum of the digits of the number X. For example, $f( 12345 ) = 1+2+3+4+5 = 15$ . Now consider the following equation: $x = a \ast f( x )^b + c \ast f( x )^d$ You have to find the number of $x$ , where $x \leq 10^{18} $ ###Input: - First line will contain $T$, number of testcases. Then the testcases follow. - Each testcase contains of a single line of input, four integers $a$, $