Problem statement is simple and straight forward . You will be given a non-negative integer P of length N and you need to check whether it's divisible by Q ?

Integer P will be given in its decimal representation with P₀ as leftmost digit and P₁ as second digit from left !

Rest of the digit can be generated from the formula :

P_i = ( 4*P_i-1 + P_i-2 ) modulo Q      for  2 <= i <= N-1

Input

The first line contains one integer T - denoting the number of test cases.

T lines follow each containing four integers P₀ , P₁ , Q and N !

Output

For each testcase output YES if the corresponding integer is divisible by Q and NO otherwise.

Constraints

• T <= 100000
• 0 < P₀ , P₁ , Q < 10
• 0 < N <= 10¹⁸

Example

Input:
4
1 4 2 2
1 4 2 1
4 2 3 2
3 4 7 3
Output:
YES
NO
YES
NO

Explanation

Value of P is 14, 1, 42, 345 in respective cases !