PFACTORS - Pisano Factors

no tags 

Given an integer n.

Find how many integers c are there such that their Pisano period is a factor of n. 

1 <= c <= 10^5

There are multiple test cases.

Input

The first line contains number of test cases, 1 <=  t <= 100

Next t lines contain an integer n each. 1 <=  n <= 10^9

Output

Output the answer to each test case on a separate line.

Example

Input:
3
6
9
10

Output: 3
2
2

hide comments
khan_cse_ruet: 2021-07-08 19:25:36

Easy , If you solved https://www.spoj.com/problems/PISANO/

khan_cse_ruet: 2021-07-08 19:24:19

@[Lakshman]
2
56
256890000
output :
14
2382

[Lakshman]: 2020-06-14 18:48:25

Thank you @Suhash.

suhash: 2020-06-14 18:44:52

@Lakshman: I just meant that the range of c is [1, 10^5], but range of Pisano(c) is not (and can be > 10^5). Your understanding of the problem seems correct. Hope that helps!

Last edit: 2020-06-14 18:50:47
[Lakshman]: 2020-06-14 18:32:49

@Suhash. Now I doubt if I understood the problem correctly. what do you mean when you say "for instance the pisano period need not be in the range [1, c]" . Pisano(1) = 1 is factor is of all numbers.

suhash: 2020-06-14 08:57:43

@Lakshman: Did you try to verify your solution with a brute force checker. Perhaps you're missing some corner cases (for instance the pisano period need not be in the range [1, c]).

[Lakshman]: 2020-06-09 18:12:23

@All Can someone give me few test cases.

2
56
256890000
what is the output

Last edit: 2020-06-09 18:12:43
[Lakshman]: 2020-06-09 13:35:22

@sarfaraz Can you please tell me why I am getting WA, I think my approach is correct.
Thanks

David: 2020-06-06 23:22:10

Java should have more time. No java solutions.
Compute pisano period of n = 1 to 10^5 in 420 ms; answer 100 test case in 20 ms.

[Rampage] Blue.Mary: 2016-01-31 08:19:49

pisano(3) = 8 (verified.)

Last edit: 2020-06-10 12:06:50

Added by:sarfaraz
Date:2016-01-22
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY