now112543e: 森友会里打音游

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

import sys
input = lambda: sys.stdin.readline()[:-1]
 
def II(base=10):
    return int(input(),base)
 
def LI():
    return list(map(int,input()))
 
def LII():
    return list(map(int,input().split()))

N = 2*10**5+1
g = [[] for _ in range(N)]
for x in range(1,N):
    for y in range(x,N,x):
        g[y].append(x)

for _ in range(II()):
    n = II()
    A = LII()
    f = [0]*(n+1)
    f2 = [0]*(n+1)
    for a in A:
        s = f2[a]
        for b in g[a]:
            s = max(s,f[b])
        f[a] = s+1
        for b in g[a]:
            f2[b] = max(f2[b],1+s)
    print(max(f))