问题 H: Expectation of Rank

Let $p$ be a prime number and ��Fp be the finite field with order $p$. Suppose $A$ is a square matrix of order $n$ and each of its entry is a random variable that uniformly distributed on ��Fp. Please calculate the expectation of the rank of $A$, i.e., $\mathbb{E}[\mathrm{rank}(A)]$.

In mathematics, a finite field, also known as a Galois field, is a set that contains a finite number of elements. These elements follow the operations of multiplication, addition, subtraction, and division, all of which satisfy the basic rules of arithmetic. The most common examples of finite fields are given by the integers mod $p$ when $p$ is a prime number.

When we say ��Fp is a finite field with order $p$, it means that ��Fp contains exactly $p$ distinct elements, with $p$ being a prime number. The elements of ��Fp are the integers $0,1,2,...,p-1$, and the operations of the field are performed modulo $p$. For instance, if $p=5$, then �5F5 is the set $0,1,2,3,4$, and in this field, $2+3=0$ and $4\times 4=1$.

The first line of the input contains an integer $T$ ($1\le T\le 50$), denoting the number of test cases.

Each of the following $T$ lines contains two integers $n,p$ ($1\le n\le 5000$, 2≤�≤1092≤p≤109), denoting the order of the square matrix $A$ and the prime number $p$.

It's guaranteed that the sum of $n$ in all test cases will not exceed $5000$.

2
2 2
2 3

812500007
802469143