\(n\) бүтін оң сандардан тұратын массив \(a_1, a_2, \dots, a_n\) берілген.

Бір операцияда екі түрлі индекс \(i\) және \(j\) (\(i \ne j\)) таңдап, келесіні орындауға болады:

\(a_i := a_i + gcd(a_i, a_j)\),

мұнда \(\gcd(x, y)\) — \(x\) және \(y\) сандарының ең үлкен ортақ бөлгіші.

Барлық массив элементтерін теңестіру үшін \(300{,}000\) операциядан аспайтын уақыт ішінде орындау қажет.

Енгізу

Бірінші жолда бір бүтін сан \(n\) (\(2 \le n \le 5000\)) беріледі.

Екінші жолда \(n\) бүтін сан \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le 10^9\)) беріледі.

Шығару

Бірінші жолда бір бүтін сан \(k\) (\(0 \le k \le 300{,}000\)) — операциялар саны.

Келесі \(k\) жолда операциялардың сипаттамасын шығарыңыз — екі сан \(i\) және \(j\) (\(1 \le i, j \le n\), \(i \ne j\)), бұл операцияда \(a_i := a_i + \gcd(a_i, a_j)\) орындалады.

Барлық операциялардан кейін массивтің барлық элементтері бірдей болуы және олардың мәндері \(10^{30}\)-нан аспауы керек.

Мысалдар

Енгізу 1

3
2 9 3

Жауап 1

5
1 3
1 2
3 1
3 2
1 2