FACVSPOW - Factorial vs Power


Consider two integer sequences f(n) = n! and g(n) = an, where n is a positive integer. For any integer a > 1 the second sequence is greater than the first for a finite number of values. But starting from some integer k, f(n) is greater than g(n) for all n >= k. You are to find the least positive value of n for which f(n) > g(n), for a given positive integer a > 1.

Input

The first line of the input contains number t – the amount of tests. Then t test descriptions follow. Each test consist of a single number a.

Constraints

1 <= t <= 100000
2 <= a <= 106

Output

For each test print the least positive value of n for which f(n) > g(n).

Example

Input:
3
2
3
4

Output:
4
7
9

hide comments
a_ranjan: 2018-06-23 18:16:04

No need for any advanced formula , just precompute the array of log (factorial) upto 10000000 and find the answer using binary search tehnique !

Last edit: 2018-06-23 18:17:04
excel_blaze: 2018-05-22 23:49:37

waste of time!!

waqar_ahmad224: 2018-03-13 19:48:17

did it without Stirling's formula , using prefix sum and log function.

vengatesh15: 2017-09-19 13:29:47

easy one with stirling's formula

holmesherlock: 2017-02-18 23:23:01

u can skip the stirling's approximation,however use of log will surely help,,and yes use double instead of float..

sy_117: 2016-02-20 00:31:48

ln(n!) = (n*ln(n))-n+(1/2*ln(2*pi*n)) !!!!!This is helpful here

Ankush : 2015-06-02 14:29:58

DId it after 2 attempts :D Loved it

/* Nitin Jaiman */: 2015-01-14 20:56:23

Stirling formula is working just think about high and low values of binary search.

ashish kumar: 2014-12-27 18:21:47

a lot of WA using stirling approx..
but got AC without stirling. just simple coding with binary search......1.39sec

vinod y: 2014-07-15 17:24:27

use printf, scanf instead of cin, cout

Last edit: 2014-07-15 17:24:42

Added by:Spooky
Date:2009-11-01
Time limit:0.985s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 NODEJS OBJC PERL6 SQLITE VB.NET
Resource:Advancement Autumn 2009, http://sevolymp.uuuq.com/