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 P0 as leftmost digit and P1 as second digit from left!

Rest of the digit can be generated from the formula:

Pi = (4*Pi-1 + Pi-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 P0, P1, Q and N!

Output

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

Constraints

  • T <= 100000
  • 0 < P0, P1, Q < 10
  • 0 < N <= 1018

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 ! 


Added by:Adarsh kumar
Date:2015-11-29
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:Own problem

hide comments
2021-12-14 18:54:30 David
Some have asked for additional test cases. This is very unlikely to provide help. Each combination of p0, p1, and q must be examined. In some cases, a specific combination of p0, p1, and q has several conditions on which n is divisible.
2018-04-28 04:41:43
This problem ruined the Friday night for my wife... but was totally worth it =) Big thumbs up for this beauty!
2016-10-17 14:50:36 :D
Problem seems very basic, but it's fun to solve and optimize. Thanks to the author.
2016-06-16 09:21:18
can u tell me why i am getting wrong answer
?? submission id is:17119699
2015-12-31 07:37:51 gomathi ganesan
Some more test cases....pls..
2015-12-25 11:30:09 DHEERAJ KUMAR
@Adk can u tell me why am i getting WA?? submission id: 15937639
2015-12-17 23:49:11 Advitiya
what's wrong with my solution id=15888473 :(
2015-12-09 11:23:18 shally darbari
can u tell me why i am getting wa?? submission id is :15812896

(reply) => You have AC for all small values of N (N<100) but many WA for larger values of N !

Last edit: 2015-12-10 19:59:44
2015-11-30 21:56:35 Bhuvnesh Jain
@adarsh kumar, can you please tell me why I am getting WA as I have tested by code on random test cases with brute solution as well and it was working fine... my last solution contains comments showing the implementation details and logic of solution as well.

(reply) => Your last submission has wrong answers for 1300 cases (approx.) for n<100 itself ! I guess you can easily find them :)

Last edit: 2015-11-30 22:54:27
2015-11-30 16:46:44 Bhuvnesh Jain
Are the submissions being rejudged?

(reply) => Did that already . You still have WA (you can check with a brute) !

Last edit: 2015-11-30 17:42:43
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.