1798C - Candy Store - CodeForces Solution

// Problem: C. Candy Store
// Contest: Codeforces - Codeforces Round 860 (Div. 2)
// URL: https://codeforces.com/contest/1798/problem/C
// Memory Limit: 256 MB
// Time Limit: 3000 ms

#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

template <typename F, typename S>
ostream& operator<<(ostream& ostream, pair<F, S>& p) {
  cout << p.first << " " << p.second;
  return ostream;
}
template <typename T>
ostream& operator<<(ostream& ostream, vector<T>& v) {
  for (auto& element : v) {
    cout << element << " ";
  }
  return ostream;
}
template <typename T>
ostream& operator<<(ostream& ostream, vector<vector<T>>& v) {
  for (auto& row : v) {
    for (auto& cell : row) {
      cout << cell << " ";
    }
    cout << "\n";
  }
  return ostream;
}
template <typename F, typename S>
istream& operator>>(istream& istream, pair<F, S>& p) {
  cin >> p.first >> p.second;
  return istream;
}
template <typename T>
istream& operator>>(istream& istream, vector<T>& v) {
  for (auto& element : v) {
    cin >> element;
  }
  return istream;
}
void __print(int x) { cerr << x; }
void __print(long x) { cerr << x; }
void __print(long long x) { cerr << x; }
void __print(unsigned x) { cerr << x; }
void __print(unsigned long x) { cerr << x; }
void __print(unsigned long long x) { cerr << x; }
void __print(float x) { cerr << x; }
void __print(double x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << '\'' << x << '\''; }
void __print(const char* x) { cerr << '\"' << x << '\"'; }
void __print(const string& x) { cerr << '\"' << x << '\"'; }
void __print(bool x) { cerr << (x ? "true" : "false"); }

template <typename T, typename V>
void __print(const pair<T, V>& x) {
  cerr << '{';
  __print(x.first);
  cerr << ',';
  __print(x.second);
  cerr << '}';
}
template <typename T>
void __print(const T& x) {
  int f = 0;
  cerr << '{';
  for (auto& i : x) cerr << (f++ ? "," : ""), __print(i);
  cerr << "}";
}
void _print() { cerr << "]\n"; }
template <typename T, typename... V>
void _print(T t, V... v) {
  __print(t);
  if (sizeof...(v)) cerr << ", ";
  _print(v...);
}
#ifndef ONLINE_JUDGE
#define debug(x...)             \
  cerr << "[" << #x << "] = ["; \
  _print(x)
#else
#define debug(x...)
#endif
#define MOD 1000000007
#define inf LLONG_MAX
#define endl "\n"
#define lp(i, a, b) for (in i = (a); i < (b); i++)
#define lpa(i, a, b) for (in i = (a); i >= (b); i--)
#define fr(i, a, b) for (in i = (a); i < (b); i++)
#define lps(i, a, b, step) for (in i = (a); i < (b); i += (step))
#define lpas(i, a, b, step) for (in i = (a); i >= (b); i -= (step))
#define pb(a) push_back(a)
#define mp(a, b) make_pair(a, b)
#define init(arr, val) memset(arr, val, sizeof(arr))
#define itv std::vector<in>::iterator
#define itum unordered_map<in, in>::iterator
#define vll vector<ll>
#define sorta(x) sort(x, x + (int)(sizeof(x) / sizeof(x[0])))
#define sortv(x) sort(x.begin(), x.end())
#define all(x) (x).begin(), (x).end()
#define pll pair<ll, ll>
#define pii pair<int, int>
#define fe first
#define se second
#define pq priority_queue
#define mset multiset
#define uset unordered_set
#define umap unordered_map
typedef long long int ll;
typedef long double ld;
typedef unsigned long long int ull;
typedef int in;
#define oset                                       \
  tree<ll, null_type, less_equal<ll>, rb_tree_tag, \
       tree_order_statistics_node_update>


ll lcm(ll a, ll b)
{
    return (a / __gcd(a, b)) * b;
}
void solve() {
	ll n,ans = 1;
	cin >> n;
	vll a(n),b(n);
	fr(i,0,n){
		cin >> a[i] >> b[i];
	}
	ll val = a[0] * b[0],num = b[0];
	fr(i,1,n){
		val = __gcd(val,a[i]*b[i]);
		num = lcm(num, b[i]);
		if(val % num){
			ans++;
			val = a[i] * b[i];
			num = b[i];
		}
	}
	cout << ans << endl;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  ll t;
  cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}