I just found this problem and i don't have any idea how to solve it .

Given an array A of n distinct elements ai such that 1 <= ai <= 10^12 and 1 <= n <= 10^5 Find the length k of any sequence of indices i1,i2,....,ik ( 1 <= i1 < i2 <....< ik <=n )

1. Such that there exists an integer m (m > 1) that satisfies ai1 = ai2 = ... = aik (mod m) .

2. k is maximized

Sample :

Input

5

6 11 16 21 26

Output

5

Given an array of size n <= 10^5 initially filed with zeros, answer two types of queries:

1 A B C : Perform the following operation arr[i] = max(arr[i],C) , where i = A (MOD B) and 1 <= i <= n .

2 I : Print value arr[I] .

Constraints : 1 <= A < B <= N and C <= 10^9

1 <= I <= N .

1 <= n , q <= 10^5 .