#include #include typedef long long int ln; #define POS(i,j) (((i)-1)*n+(j)-1) #define MIN(a,b) ((a)<(b)?(a):(b)) void run(void){ const int n=1500; ln *dp=(ln *)malloc(sizeof(ln)*n*n); int i,j; for(i=1;i<=n;i++){ dp[POS(1,i)]=1; } for(i=2;i<=n;i++){ dp[POS(i,1)]=i; for(j=2;j<=n;j++){ dp[POS(i,j)]=MIN(dp[POS(i-1,j)]+dp[POS(i,j-1)],1000000000000001LL); } } int q; scanf("%d",&q); for(i=0;i