BSEXP - Base Exploration

Problem Statement is easy, for a given number N, you have to print the base B such that if we write N in base B then it would contain most 0's at the end.

If more then one such base exist, which satisfy the given condition then print the smallest such base.

Input

The first line of the input consist of a single integer number t which determines the number of tests.

In each of next t lines there is a single integer number N.

Constraints

  • 0 < t ≤ 105
  • 2 ≤ N ≤ 1012

Output

Output contains one line with one integer B such that N written in base B has the most zeros at the end and is the smallest B with this property.

Example

Input:
2
72
18

Output:
2
3

Explanation

The answer for N=72 is B=2, because 72=10010002 (72 written in base 2) has 3 zeros at the end.

Using base 3, we only get 2 zeroes at the end (because 72=22003),

using base 6 would also give us 2 zeros, and no other base would give us more than 1 zero

For 18, 18=100102 and 18=2003 so answer will be 3.

Note: Test case were regenerated on 23 June 2020.

As rejudge is disabled by SPOJ please submit your code again.


Added by:Amit
Date:2020-06-22
Time limit:1.5s-4.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All

hide comments
2021-07-10 15:48:18
only 15 testcases passed,rest gives tle
2021-03-24 18:51:44 anonymous
The problem statement should make clear that unary numeral system, i.e., base 1, is not a valid answer.
2020-08-29 17:25:32 Rafail Loizou
[NG]: Testdata are correct now and 39 AC's prove it. Please don't spell out algorithm details in comments.

Yeah I'm sorry. I found what the problem was. I had to go 1 more step deeper in the maths world XD. Sorry man but it's been like a whole day I'm trying to crack what the problem was. Thanks for the response tho it made me feel safe and will make the next ones to try feel safe as well.

Last edit: 2020-08-29 18:20:58
2020-08-16 20:46:48
bad tc. btw passed


Last edit: 2020-08-16 20:47:14
2020-06-25 13:12:12
@devilwolverine Not very fast :-).
2020-06-25 12:38:04 Vipul Srivastava
does this require [spoiler] algorithms?

Author: nope, I think even brute force will work.

Last edit: 2020-06-25 13:27:03
2020-06-23 03:12:27
[Angry rant removed]

Author Reply: I already replied that to @Scape. And I'm really sorry.

[NG]: I'm a hothead and that means sometimes an asshole. Sorry. Please doublecheck testdata *before* problem is published; I took half an hour to find the defect, most of it trying to debug my correct solution, meanwhile multiple people were going through the same. That's hours of wasted time on aggregate, not to mention all the unnecessary frustration.

Author Reply: I'm a little bit new to SPOJ problem setting. Just learning from my mistake. Again I'm so sorry.

Last edit: 2020-06-23 06:46:06
2020-06-22 22:48:17 Scape
@offamitkumar you should not delete comments. It's not nice. I see that you did the same thing in your previous problem (IFACTO) and other users complained about it as well. And if you've regenerated the test data you should rejudge all submissions too.

Author Reply: I'm really sorry, but I didn't deleted the comments. For testing, I moved this problem from classical to none section then after adding new testcases I added again it to classical section. And comment were gone you can check it yourself.
Also I tried to rejudge but it shows that rejudge is disable.

-> Sorry I did not realize that. You'll get used to it soon. I understand it can be a bit confusing as a new problem setter.

Last edit: 2020-06-23 19:39:40
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.