Far far away from here ,there is a world of peace ,Byteland .But this morning ,Laskar-e-trishul ,a terrorist Organisation has
threatened the people of Byteland declaring that the peaceful land will be bombarded today.The Intelligence of Byteland has intercepted
an encrypted key which is claimed as the key of Bomb.

Programmers were called to Decrypt the key but they were stuck at a problem.

 

It is required to first evaluate f(A,B) and then key is equal to the no. of pairs (L,M) where

1 such that gcd of L and M is C.
Now Mayer of Byteland is looking for you as his last option.
Note:A^B means A raise to the power B
f(A,B)=K(A^B)
where

K(x)
{
s=0
while(x)
{
s=s+x%10;
x=x/10;
}
if(s>9)
s=K(s);
return s;
}

Input:

First Line contains T=No. of test Cases
For each test Case:
Each Line consists of four integers A, B , C, P corresponding to each test case.

Output:

For each test case, output the number of desired pairs of (L,M).

Constraints:

1
11

INPUT

1
2 2 2 6

OUTPUT

10