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 !