SP25810 MATNUM - Divisibility Test

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 $ _{0} $** as leftmost digit and **P $ _{1} $** 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

The first line contains one integer **T** - denoting the number of test cases. **T** lines follow each containing four integers **P $ _{0} $** , **P $ _{1} $** , **Q** and **N** !

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