SPOJ.com - Problem LKID

LKID - Identity crisis(Medium)

no tags

As lucky have solved IDC1948 with easy constraints .Now he would like to solve the problem with some serious constraints. But as you know lucky is not very good in solving hard problems he need your help, can you help him.

For every given number n we define x(n) as distance from n to the first number greater than or equal to n in form of 99...99. For example x(100) = 899, x(45) = 54, etc. Given several n numbers you have to find the Zp, where x(n)≡n mod p.

Input

First line of input contains one number T (0 < T < 1001) - the number of test cases. In each of the next T lines contains one number each to represent n.

Output

In each line you have to write one number - the least p > 1 that x(n) ≡ n mod p. If there is no such p the line should contain -1.

Example

Input:
2
234
5

Output:
3
-1

Explanation

x(234) = 765. 765 mod 3 = 0, 234 mod 3 = 0 => 765 ≡ 234 mod 3

NOTE: Time limit is allowed to pass with slow languages.

My own C++ solution passed under 0.41s. Have fun;)

Submit solution!

hide comments

< Previous 1 2 Next >

	Anchrondite: 2015-04-05 15:20:51 @ Lakshman why the solution with n^0.25 complexity giving TLE? --(Lakshman)-->Your isPrime function is very slow, You may try Rabin Miller prime testing . You can also check if the number is divisible by small prime till 500. Hope this helps. @Lakshman -- Thanks it helped ...AC :) Last edit: 2015-04-11 22:00:55
	Sahil Sharma: 2015-01-11 12:24:37 Could someone please explain what Francky meant by "pbC", "pbF" and "pbA"? Thanks --(Francky)--> I mean that this problem is nothing but FACT1(IDC1948), and as it is nothing else but a clone, and do not consist of new task. I still believe this problem should be moved to tutorial ; @Lakshman : please move it. -Lakshman->Done!! Last edit: 2015-01-11 13:52:15
	[Lakshman]: 2015-01-11 12:24:37 Thanks @Francky for clarification. I have moved LCMSUMH to tutorial, But I am leaving this LKID to Classical section.
	Francky: 2015-01-11 12:24:37 Yes, the original problem has weak constraints and had some issues at time of publications ; it's not the best problem... Yes, the 29digits was ironic ;-) But, let pbC a new problem as pbF ( pbA ). That is here, and with LCMSUMH. I consider pbC a new problem only if pbF or pbA is quite new. For IDC1948, pbA was quite new, so OK. Now let pbD as pbF( pbB ) with new constraints ; will it impact method in pbF and/or pbB ? if it impact the specific(new) problem then it's ok. If it impact only a common pbF, then I think it's a duplicate and should be moved to tutorial. Especially when pbF is a sensitive one. That was the reason for the 29d ironic allusion. @[Lakshman] : you're a talented psolver, I'm sure you understand that very well and you'll move them by yourself. Thanks for your comprehension. Moved to tutorial doesn't mean it's a bad problem !!! Your problem is better, but here the pbA part is exactly the same. I think the best problem would have been one where we can get AC with pbF and O(n^0.5) with time >0.01s.
	Mitch Schwartz: 2015-01-11 12:24:37 I'm pretty sure the 10^29 suggestion was ironic. :p Last edit: 2015-01-02 08:53:12
	[Lakshman]: 2015-01-11 12:24:37 @EB Members I will leave it on you. If you think both are duplicate problems you can move it to tutorial.
	Min_25: 2015-01-11 12:24:37 In fact, your problems LKID and LCMSUMH are the almost duplicates of FACT1 for those who have solved the original problems. Last edit: 2015-01-02 04:40:42
	Francky: 2015-01-11 12:24:37 I don't think this edition need a better specific algorithm than the original, where brute force can't pass. It's true, the first have low constraints and it's easy to get 0.00s even with slow languages, but this one only need a non specific part of code... Why not set an edition with 29digits ? My 2c. I prefer when there's no duplicate, or when a specific improvement is needed. --Lakshman-> The original edition of this problem have very poor constraints and any one can get AC with ultra basic(brute force algorithm by trying all prime numbers). The reason why I choose 10^18 is to allow c/c++.. and other language(no support of BigInteger) can be used with proper algorithm, and that's why I choose its name (Medium), so there is still place for Hard version. --Francky--> Ultra brute force is on pbF part, not on pbA part (see comment ↑ ). So this edition doesn't change the specific part. Last edit: 2015-01-02 11:45:02
	anurag garg: 2015-01-11 12:24:37 Lakshman can you tell me what is wrong in my last submission. thanks
	legrand: 2015-01-11 12:24:37 @Lakshman - what's wrong in my submission 12394776 is it for big values of n? Lakshman--> Your code is printing only 2 for all cases. are you sure? my code works well for the example testcases. Lakshman-->http://ideone.com/uncGuo check this -I have found this problem only for 1e18<=n<1e19. can you confirm n<1e18 ? Lakshman-->I checked your submission 12396665 and it is printing same 2 for the input file which contains n > 1 & n < 10001 Even if you correct this your Algorithm will give TLE. -my input and output before n=1000 for submission 12396665 is the following http://ideone.com/VD8fSt , output values are not 2. Why can it be 2 on spoj? Lakshman--> Your last two submission are Okay. They have many correct answers. I also checked your solution on My system now they are fine. Earlier they were also good but don't know why it was only 2. You need at least complexity between O(n^0.25) or O(n^.30). Good Luck Last edit: 2014-09-18 12:02:16

Submit solution!

Added by:	[Lakshman]
Date:	2014-03-25
Time limit:	1s-6s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: ASM64
Resource:	IDC1948